leetcode 268 丢失的数字

一、题目描述

二、解题思路

整体思路

可以采用位运算的思想来解决这个问题。

具体思路

由异或运算的运算律a^a=0，a^0=a可以得到，成对的数字可以通过异或运算进行消除。因此，我们可以将[0,n]区间内的整数进行异或操作，再将nums中的数字进行异或，成对消除后，剩下的数字即为丢失的数字，直接返回r即可。

三、代码实现

时间复杂度：T(n)=O(n)

空间复杂度：S(n)=O(1)

class Solution {
public:int missingNumber(vector<int>& nums) {int r=0;for(int i=0;i<=nums.size();i++) r^=i;for(auto x:nums) r^=x;return r;}
};