leetcode：268. 丢失的数字

题目

给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。
nums 中的所有数字都 独一无二，0 <= nums[i] <= n。

示例：

  1. 输入：nums = [3,0,1]
  2. 输出：2
  3. 解释：n = 3，因为有 3 个数字，所以所有的数字都在范围 [0,3] 内。2 是丢失的数字，因为它没有出现在 nums 中。
  1. 输入：nums = [0,1]
  2. 输出：2
  3. 解释：n = 2，因为有 2 个数字，所以所有的数字都在范围 [0,2] 内。2 是丢失的数字，因为它没有出现在 nums 中。
  1. 输入：nums = [9,6,4,2,3,5,7,0,1]
  2. 输出：8
  3. 解释：n = 9，因为有 9 个数字，所以所有的数字都在范围 [0,9] 内。8 是丢失的数字，因为它没有出现在 nums 中。
  1. 输入：nums = [0]
  2. 输出：1
  3. 解释：n = 1，因为有 1 个数字，所以所有的数字都在范围 [0,1] 内。1 是丢失的数字，因为它没有出现在 nums 中。

解答 & 代码

利用性质：**a^a=0**.
将 [0, n] 这 n+1 个数和数组 nums 中的 n 个数全部进行与操作，最终得到的结果就是缺失的数字 

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

复杂度分析：

  • 时间复杂度 O(n)：
  • 空间复杂度 O(1)：

执行结果：

  1. 执行结果：通过
  3. 执行用时：16 ms, 在所有 C++ 提交中击败了 74.46% 的用户
  4. 内存消耗：17.5 MB, 在所有 C++ 提交中击败了 65.70% 的用户