LintCode 寻找缺失的数题目分析方法二 交换法

题目

给出一个包含 0 .. N 中 N 个数的序列,找出0 .. N 中没有出现在序列中的那个数。

样例 N = 4 且序列为 [0, 1, 3] 时,缺失的数为2。

分析

方法一: 求和法 由于缺失了一个元素,那么我们可以用高斯公式先求出完整的序列的和,然后求出给定数组的和,最后相减就是缺失的元素,效率高

public class Solution {
    /**    
     * @param nums: an array of integers
     * @return: an integer
     */
    public int findMissing(int[] nums) {
        // write your code here
        
        int n = nums.length;
        long sum=0;
        for(int i=0;i<n;i++) {
            sum += nums[i];
        }
        
        return (int) (0.5 * (n+1) * (n) - sum);
    }
}

方法二 交换法

我们已经知道每个位置的元素应该出现的值,那么就遍历一遍数组,如果nums【i】!=i,就把他换到它应该在的位置,最后遍历一遍就得出那个数

public class Solution {
    /**    
     * @param nums: an array of integers
     * @return: an integer
     */
    public int findMissing(int[] nums) {
        // write your code here
        int n = nums.length, i = 0;
        while (i<n) {
            while (nums[i]!=i && nums[i]<n) {
                int t = nums[i];
                nums[i] = nums[t];
                nums[t] = t;
            }
            ++i;
        }
        for (i=0; i<n; ++i)
            if (nums[i]!=i) return i;
        return n;
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

单调栈小结

18010
来自专栏Hadoop数据仓库

HAWQ + MADlib 玩转数据挖掘之(三)——向量

一、定义         这里不讨论向量严格的数学定义。在Madlib中,可以把向量简单理解为矩阵。矩阵是Madlib中数据的基本格式,当矩阵只有一维时,就是向...

249100
来自专栏python读书笔记

《python算法教程》Day10 - 平面最近点对问题平面最小点对问题介绍代码演示

今天是《python算法教程》的第10篇读书笔记。笔记的主要内容是使用python实现求最小点对的时间复杂度为O(nlogn)的算法。 平面最小点对问题介绍 在...

749120
来自专栏AI派

Numpy 修炼之道 (7)—— 形状操作

无论是ravel、reshape、T,它们都不会更改原有的数组形状,都是返回一个新的数组。

30230
来自专栏数据结构与算法

拉格朗日插值

存在性和唯一性的证明以后再补。。。。 拉格朗日插值 拉格朗日插值,emmmm,名字挺高端的:joy: 它有什么应用呢? 我们在FFT中讲到过 设n-1次多项式为...

30570
来自专栏数据处理

TensorFlow入门1-minist

18130
来自专栏Python小屋

Python标准库random用法精要

random标准库主要提供了伪随机数生成函数和相关的类,同时也提供了SystemRandom类(也可以直接使用os.urandom()函数)来支持生成加密级别要...

31660
来自专栏郭耀华‘s Blog

TensorFlow 常用函数汇总

83220
来自专栏机器学习算法原理与实践

用scikit-learn学习谱聚类

    在谱聚类(spectral clustering)原理总结中,我们对谱聚类的原理做了总结。这里我们就对scikit-learn中谱聚类的使用做一个总结。

28640
来自专栏10km的专栏

faster rcnn:assert (boxes[:, 2] >= boxes[:, 0]).all()分析塈VOC2007 xml坐标定义理解

在进行faster rcnn训练的时候,报了一个断言错误 File “/py-faster-rcnn/tools/../lib/datasets/imdb.p...

52350

扫码关注云+社区

领取腾讯云代金券