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?

分析

本题的意思是，从1到n的整数，其中某个数丢失了，替代它的是0。要我们找出这个丢失的数。

方法1，我们可以用公式计算出从1到n的和，减去实际数组的总和，差值就是那个丢失的数。

方法2，利用异或位运算，把数组中的每一个数，与1到n进行按位异或，最后剩下的，就是丢失的数。

方法3，二分查找。首先把数组排序，设中间元素为nums[mid]，如果nums[mid]的值大于其下标，说明丢失的数字在左边，反之则在右边。时间复杂度O(nlogn)，比前面两个方法慢，但是如果题目给的数组是事先排好序的，那么复杂度就是O(log n)，所以这个方法还是很有意义的。

解法1

  1. // Missing Number
  2. // Time Complexity: O(n), Space Complexity: O(1)
  3. public class Solution {
  4.     public int missingNumber(int[] nums) {
  5.         int sum = 0;
  6.         for (int x : nums) {
  7.             sum += x;
  8.         }
  9.         final int n = nums.length;
  10.         final int sumExpected = (n * (n + 1)) / 2;
  11.         return sumExpected - sum;
  12.     }
  13. }

解法2

  1. // Missing Number
  2. // Time Complexity: O(n), Space Complexity: O(1)
  3. public class Solution {
  4.     public int missingNumber(int[] nums) {
  5.         int result = 0;
  6.         for (int i = 0; i < nums.length; ++i) {
  7.             result ^= (i+1) ^ nums[i];
  8.         }
  9.         return result;
  10.     }
  11. }

解法3

  1. // Missing Number
  2. // Time Complexity: O(nlogn), Space Complexity: O(1)
  3. public class Solution {
  4.     public int missingNumber(int[] nums) {
  5.         Arrays.sort(nums);
  6.         int begin = 0;
  7.         int end = nums.length;
  8.         while (begin != end) {
  9.             final int mid = begin + (end - begin) / 2;
  10.             if (mid < nums[mid]) end = mid;
  11.             else begin = mid + 1;
  12.         }
  13.         return end;
  14.     }
  15. }

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/java/bitwise-operations/missing-number.html