LeetCode268 - Missing Number

https://leetcode.com/articles/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?

Other solution: convert index(whose value is a[i]) to negative.

X. Using XOR

http://storypku.com/2015/10/leetcode-question-268-missing-number/

    int missingNumber(vector<int>& nums) {

        int size = nums.size();

        

        int res = 0;

        

        for(int i=0; i < size + 1; i++) {

            res ^= i;

        }

        

        for(int i=0; i < size; i++) {

            res ^= nums[i];

        }

        

        return res;

    }

X.
public:
    int missingNumber(vector<int>& nums) {
        int n = (1+nums.size())*nums.size()/2;
        for (int i = 0; i < nums.size(); i++) {
            n -= nums[i];
        }
        return n;
    }
http://www.neozone.me/leetcode268.html

已知一个数组包含了0到n的所有整数，除了一个数不在里面。求这个缺失的数。

如果不缺这个数，根据等差数列求和公式，所有的数加起来应该等于(1 + n) * n / 2。但是现在少了某个数x，此时求和的结果应该比(1 + n) * n / 2正好少x。

注意，当n很大的时候直接计算(1 + n) * n / 2会导致溢出，因此我们采用一边加一边减的方式。

    public int missingNumber(int[] nums) {

        int temp = nums.length;

        for(int i = 0; i < nums.length; i++){

            temp = temp + i - nums[i];

        }

        return temp;

    }

X. http://blog.csdn.net/xudli/article/details/48286379

把nums[i]放到i的位置上.  nums[i] != i的即为missing number.

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

  public int missingNumber(int[] nums) {

    int expectedSum = nums.length * (nums.length + 1) / 2;

    int actualSum = 0;

    for (int num : nums)

      actualSum += num;

    return expectedSum - actualSum;

  }

http://shibaili.blogspot.com/2015/08/day-121-264-ugly-number-ii.html

    int missingNumber(vector<int>& nums) {

        for (int i = 0; i < nums.size(); i++) {

            int target = nums[i];

            while (target >= 0 && target < nums.size() && nums[target] != target) {

                swap(nums[i],nums[target]);

                target = nums[i];

            }

        }

         

        for (int i = 0; i < nums.size(); i++) {

            if (i != nums[i]) return i;

        }

        return nums.size();

    }

  public int missingNumber(int[] nums) {

    int missing = nums.length;

    for (int i = 0; i < nums.length; i++) {

      missing ^= i ^ nums[i];

    }

    return missing;

  }

X.

  public int missingNumber(int[] nums) {

    Set<Integer> numSet = new HashSet<Integer>();

    for (int num : nums)

      numSet.add(num);

    int expectedNumCount = nums.length + 1;

    for (int number = 0; number < expectedNumCount; number++) {

      if (!numSet.contains(number)) {

        return number;

      }

    }

    return -1;

  }

X. Sorting

  public int missingNumber(int[] nums) {

    Arrays.sort(nums);

    // Ensure that n is at the last index

    if (nums[nums.length - 1] != nums.length) {

      return nums.length;

    }

    // Ensure that 0 is at the first index

    else if (nums[0] != 0) {

      return 0;

    }

    // If we get here, then the missing number is on the range (0, n)

    for (int i = 1; i < nums.length; i++) {

      int expectedNum = nums[i - 1] + 1;

      if (nums[i] != expectedNum) {

        return expectedNum;

      }

    }

    // Array was not missing any numbers

    return -1;

  }