Leetcode 268.Missing Number

发表于   |   分类于   |  

268.Missing Number的题目大意为:
给出一个数组，包含n个数(取自0~n之间)，让你找出缺少了哪个数.

通过数组的大小可以知道n为多大，有两种方法来解这道题。

1.求和法

0, 1, 2, …, n这n+1个数的和我们可以求出, 减去给出的n个数之和, 差值就是缺少的那个数.
需要注意注意一点, 直接求和如果数值过大可能会overflow, 所以要边加边减.

C++代码: github

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int ret = nums.size();
        for(int i = 0;i < nums.size();i++)
        {
            ret -= nums[i];
            ret += i;
        }
        return ret;
    }
};

2.位操作

我们已经知道了0~n这n+1个数, 又知道了给出的n个数. 所以缺失的数只出现了一次, 其他数字出现了两次.

xor 运算有以下的性质:

x^x = 0
0^x = x

所以, 将所有的数做异或运算, 运算的结果即为缺失的数.

C++代码: github

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int ret = nums.size();
        for(int i = 0;i < nums.size();i++)
        {
            ret ^= nums[i];
            ret ^= i;
        }
        return ret;
    }
};