Leetcode.268.Missing Number

题目

给定一个数组，里面数字是从0到n，但是缺了一个数，找出缺的数字。

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

思路1

使用n+1的数组做标记，有这个数就标记为1，没有就标记为0。最后找出为0的数。

int missingNumber1(vector<int>& nums) {
    vector<int> vec(nums.size()+1,0);

    for (int a : nums) {
        vec[a] = 1;
    }

    for (int i = 0;i < vec.size();i++) {
        if (vec[i] == 0) {
            return i;
        }
    }

    return (int)nums.size();
}

思路2

位运算，异或运算。分别对前n个数做异或，对给定数做异或，然后对两者再做异或，即可找到缺失的数。

  int missingNumber(vector<int>& nums)
  {
      if (nums.empty()) return 0;
      int all = 0x0;
      int cur = 0x0;
      for (int i = 0; i < nums.size()+1; i++) {
          all = all ^ i;
          if (i != nums.size()) {
              cur = cur ^ nums[i];
          }
      }
      return (all ^ cur);
  }

总结

神奇的异或操作，进行两次异或，负负得正的原理。