Find the Missing Number

Question

Problem Statement

Given an array contains N numbers of 0 .. N, find which number doesn’t exist in the array.

Example

Given N = 3 and the array [0, 1, 3], return 2.

Challenge

Do it in-place with O(1) extra memory and O(n) time.

題解1 - 位運算

和找單數的題類似，這裡我們不妨試試位運算中 Exlcusive Or (XOR) 的思路。最開始自己想到的是利用相鄰項異或結果看是否會有驚喜，然而發現 a^(a+1) != a^a + a^1 之後眼淚掉下來… 如果按照找單數的做法，首先對陣列所有元素異或，得到數x1, 現在的問題是如何利用x1得到缺失的數，由於找單數中其他數都是成對出現的，故最後的結果即是單數，這裏每個數都是單數，怎麼辦呢？我們現在再來分析下如果沒有缺失數的話會是怎樣呢？假設所有元素異或得到數x2, 數x1和x2有什麼差異呢？假設缺失的數是x0，那麼容易知道x2 = x1 ^ x0, 相當於現在已知x1和x2，要求x0. 根據 Bit Manipulation 中總結的交換律，x0 = x1 ^ x2.

位運算的題往往比較靈活，需要好好利用常用等式變換。

Java

  1. public class Solution {
  2.     /**
  3.      * @param nums: an array of integers
  4.      * @return: an integer
  5.      */
  6.     public int findMissing(int[] nums) {
  7.         if (nums == null || nums.length == 0) return -1;
  9.         // get xor from 0 to N excluding missing number
  10.         int x1 = 0;
  11.         for (int i : nums) {
  12.             x1 ^= i;
  13.         }
  15.         // get xor from 0 to N
  16.         int x2 = 0;
  17.         for (int i = 0; i <= nums.length; i++) {
  18.             x2 ^= i;
  19.         }
  21.         // missing = x1 ^ x2;
  22.         return x1 ^ x2;
  23.     }
  24. }

源碼分析

略

複雜度分析

遍歷原陣列和 N+1大小的陣列，時間複雜度 O(n), 空間複雜度 O(1).

題解2 - 桶排序

非常簡單直觀的想法——排序後檢查缺失元素，但是此題中要求時間複雜度爲 O(n), 因此如果一定要用排序來做，那一定是使用非比較排序如桶排序或者計數排序。題中另一提示則是要求只使用 O(1) 的額外空間，那麼這就是在提示我們應該使用原地交換。根據題意，元素應無重複，可考慮使用桶排，索引和值一一對應即可。第一重 for 循環遍歷原陣列，內循環使用 while, 調整索引處對應的值，直至相等或者索引越界爲止，for 循環結束時桶排結束。最後再遍歷一次陣列找出缺失元素。

初次接觸這種題還是比較難想到使用桶排這種思想的，尤其是利用索引和值一一對應這一特性找出缺失元素，另外此題在實際實現時不容易做到 bug-free, while 循環處容易出現死循環。

Java

  1. public class Solution {
  2.     /**
  3.      * @param nums: an array of integers
  4.      * @return: an integer
  5.      */
  6.     public int findMissing(int[] nums) {
  7.         if (nums == null || nums.length == 0) return -1;
  9.         bucketSort(nums);
  10.         // find missing number
  11.         for (int i = 0; i < nums.length; i++) {
  12.             if (nums[i] != i) {
  13.                 return i;
  14.             }
  15.         }
  17.         return nums.length;
  18.     }
  20.     private void bucketSort(int[] nums) {
  21.         for (int i = 0; i < nums.length; i++) {
  22.             while (nums[i] != i) {
  23.                 // ignore nums[i] == nums.length
  24.                 if (nums[i] == nums.length) {
  25.                     break;
  26.                 }
  27.                 int nextNum = nums[nums[i]];
  28.                 nums[nums[i]] = nums[i];
  29.                 nums[i] = nextNum;
  30.             }
  31.         }
  32.     }
  33. }

源碼分析

難點一在於正確實現桶排，難點二在於陣列元素中最大值 N 如何處理。N 有三種可能：

  1. N 不在原陣列中，故最後應該返回 N
  2. N 在原陣列中，但不在陣列中的最後一個元素
  3. N 在原陣列中且在陣列最後一個元素

其中情況1在遍歷桶排後的陣列時無返回，最後返回 N.

其中2和3在 while 循環處均會遇到 break 跳出，即當前這個索引所對應的值要麼最後還是 N，要麼就是和索引相同的值。如果最後還是 N, 也就意味着原陣列中缺失的是其他值，如果最後被覆蓋掉，那麼桶排後的陣列不會出現 N, 且缺失的一定是 N 之前的數。

綜上，這裏的實現無論 N 出現在哪個索引都能正確返回缺失值。實現上還是比較巧妙的，所以說在沒做過這類題時要在短時間內 bug-free 比較難，當然也可能是我比較菜…

另外一個難點在於如何保證或者證明 while 一定不會出現死循環，可以這麼理解，如果 while 條件不成立且未出現nums.length這個元素，那麼就一定會使得一個元素正確入桶，又因爲沒有重復元素出現，故一定不會出現死循環。

複雜度分析

桶排時間複雜度 O(n), 空間複雜度 O(1). 遍歷原陣列找缺失數時間複雜度 O(n). 故總的時間複雜度爲 O(n), 空間複雜度 O(1).