LeetCode 268. Missing Number

原题链接在这里：https://leetcode.com/problems/missing-number/

题目：

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?

题解：

再刷时，感觉好极了！

与First Missing Positive相似。第一遍把nums[i]放到对应位置上，第二遍看谁不在对应位置上. 若是都在位置上说明missing number 是n, 也就是nums.length.

Time Complexity: O(n). Space: O(1).

AC Java:

 1 public class Solution {
 2     public int missingNumber(int[] nums) {
 3         if(nums == null || nums.length == 0){
 4             return 0;
 5         }
 6         for(int i = 0; i<nums.length; i++){
 7             if(nums[i] >= 0 && nums[i] < nums.length && nums[i] != nums[nums[i]]){
 8                 swap(nums, i, nums[i]);
 9                 i--;
10             }
11         }
12         for(int i = 0; i<nums.length; i++){
13             if(nums[i] != i){
14                 return i;
15             }
16         }
17         return nums.length;
18     }
19     private void swap(int [] nums, int i, int j){
20         int temp = nums[i];
21         nums[i] = nums[j];
22         nums[j] = temp;
23     }
24 }

第一种方法是求和，然后挨个减掉，剩余的值就是结果，因为如果是全的，那么sum = n*(n+1)/2.

Time Complexity: O(nums.length). Space: O(1).

第二种方法是从前往后做bit Manipulation, res初始为0，每次保留结果和 (i+1)^nums[i] 取结果，方法非常巧妙。

Time Complexity: O(nums.length). Space: O(1).

AC Java:

 1 public class Solution {
 2     public int missingNumber(int[] nums) {
 3         /*
 4         //Method 1
 5         if(nums == null || nums.length == 0){
 6             return 0;
 7         }
 8         int n = nums.length;
 9         int sum = 0;
10         for(int i = 0; i<nums.length; i++){
11             sum+=nums[i];
12         }
13         return n*(n+1)/2 - sum;
14         */
15         //Method 2
16         if(nums == null || nums.length == 0){
17             return 0;
18         }
19         int res = 0;
20         for(int i = 0; i<nums.length; i++){
21             res ^= (i+1)^nums[i];
22         }
23         return res;
24     }
25 }

跟上Find All Numbers Disappeared in an Array.