LeetCode#268. Missing Number

发表于

LeetCode#268. Missing Number

Given an array containing n distinct numbers taken from 0, 1, 2, …, n, find the one that is missing from the array.

Example 1

1
2
Input: [3,0,1]
Output: 2

Example 2

1
2
Input: [9,6,4,2,3,5,7,0,1]
Output: 8

Note:
Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?

分析

参考之前分析的LeetCode#136，修改数组元素是最简单直接的方法。

修改数组解法

由于数组中可能包含0，0的正负数都是0，因此不能使用取负数的方式来完成。但是因为数组总是[0, array.length]点真子集，那么我们只需要使访问过的数不在这个范围即可。如下：

1
2
3
4
5
6
7
8
9
10
11
int missing(nums) // nums is a integers array, and this function return the missing number
  for (n in nums)
    n = n < 0 ? (-n + 1) : n
    if (n < nums.length)
      nums[n] = -nums[n] - 1         // 取负数并减1，避开0

  for (i = 0; i < nums.length; i++)  // 找到唯一的非负数的下标，下标就是没有出现过的数
    if (nums[i] >= 0)
      return i

  return nums.length

异或解法

那么，使用异或方法能不能解决这个问题呢？我们可以看到给定的数组中不会存在重复的数，但是数组总是[0, array.length]的真子集，而其补集只有一个数。那么，问题就很简单了，只要我们把数组和[0, array.length]做异或，就能找到唯一的那个数了。如下：

1
2
3
4
5
6
7
int missing(nums) // nums is a integers array, and this function return the missing number
  int result = nums.length
  for (i = 0; i < nums.length; i++)
    result ^= i
    result ^= nums[i]

  return nums.length

通过这道题以及LeetCode#136，可以发现在适当的情境下，使用位运算总是能简洁、优雅地解决问题。