LeetCode 268. Missing Number缺失数字 (C++/Java)

题目：

Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.

Example 1:

Input: [3,0,1]

Output: 2

Example 2:

Input: [9,6,4,2,3,5,7,0,1]

Output: 8

Note:
Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?

分析：

给定一个包含 0, 1, 2, ..., n 中 n 个数的序列，找出 0 .. n 中没有出现在序列中的那个数。

最先想到将数组进行排序，再依次判定数和索引是否对应，首次不对应的索引便是缺失的数。不过由于需要对数组进行排序，这样时间复杂度就不会是线性的了。

也可以创建一个集合，将数组中元素添加进集合中，再从0到n对集合进行查询，不在集合内的便是缺失的数。不过这样空间复杂度就不是常数级的了。

我们知道所给的数的序列是从0到n，且只缺失一个数，根据高斯求和公式，可以快速求得0到n这n+1个数的和，再减去序列中的n个数，剩下的便是缺失的数。

还可以利用异或运算（XOR），我们知道对一个数进行两次完全相同的异或运算会得到原来的数，即

a ^ b ^ b = a

a ^ a = 0

根据题目我们知道，未缺失的数，在[0-n]和数组中各出现了一次，而缺失的数只在[0-n]中出现了一次，根据这个条件和异或的特性可以通过一次循环求得缺失数。

假设所给的序列为0,1,3,4，我们可以求得

missing = 4 ^ 0 ^ 0 ^ 1 ^ 1 ^ 2 ^ 3 ^ 3 ^ 4

　　　 = (4 ^ 4) ^ (0 ^ 0) ^ (1 ^ 1) ^ 2 ^ (3 ^ 3)

　　　 = 0 ^ 0 ^ 0 ^ 0 ^ 2

　　　 = 2

程序：

C++

//use math

class Solution {

public:

    int missingNumber(vector<int>& nums) {

        int n = nums.size();

        int res = (+n)*n/;

        for(int q:nums)

            res -= q;

        return res;

    }

};

//use xor

class Solution {

public:

    int missingNumber(vector<int>& nums) {

        int res = nums.size();

        for(int i = ; i < nums.size(); ++i){

            res = res ^ i ^ nums[i];

        }

        return res;

    }

};

Java

class Solution {

    public int missingNumber(int[] nums) {

        int n = nums.length;

        int res = (1+n)*n/2;

        for(int q:nums)

            res -= q;

        return res;

    }

}

class Solution {

    public int missingNumber(int[] nums) {

        int res = nums.length;

        for(int i = 0; i < nums.length; ++i){

            res = res ^ i ^ nums[i];

        }

        return res;

    }

}

巴特西

LeetCode 268. Missing Number缺失数字 (C++/Java)

题目：

分析：

程序：

最新文章

热门文章