Given an array containing n distinct numbers taken from 0, 1, 2, …, n, find the one that is missing from the array.
For example, Given nums = [0, 1, 3] return 2.
Note: Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?
方法一、xor運算的方法
int missingNumber(vector<int>& nums) { int res = nums.size(); for(int i = 0; i < nums.size(); i++){ res ^= i; res ^= nums[i]; } return res; }方法二、減的方法
int missingNumber(vector<int>& nums) { int res = nums.size(); int sum = (res + 1)*res /2; for(int i = 0; i < nums.size(); i++){ sum -= nums[i]; } return sum; }方法三、二分查找
int missingNumber(vector<int>& nums) { sort(nums.begin(),nums.end()); int left = 0; int right = nums.size(); int mid = (left + right) / 2; while(left < right){ mid = (left + right) / 2; if(nums[mid] > mid) right = mid; else left = mid + 1; } return left; }新聞熱點
疑難解答
