# Find the Missing Number
### Source
- lintcode: [(196) Find the Missing Number](http://www.lintcode.com/en/problem/find-the-missing-number/)
- [Find the Missing Number - GeeksforGeeks](http://www.geeksforgeeks.org/find-the-missing-number/)
### Problem
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)O(1)O(1) extra memory and O(n)O(n)O(n) time.
### 題解1 - 位運(yùn)算
和找單數(shù)的題類(lèi)似，這里我們不妨試試位運(yùn)算中異或的思路。最開(kāi)始自己想到的是利用相鄰項(xiàng)異或結(jié)果看是否會(huì)有驚喜，然而發(fā)現(xiàn) `a^(a+1) != a^a + a^1` 之后眼淚掉下來(lái)... 如果按照找單數(shù)的做法，首先對(duì)數(shù)組所有元素異或，得到數(shù)`x1`, 現(xiàn)在的問(wèn)題是如何利用`x1`得到缺失的數(shù)，由于找單數(shù)中其他數(shù)都是成對(duì)出現(xiàn)的，故最后的結(jié)果即是單數(shù)，這里每個(gè)數(shù)都是單數(shù)，怎么辦呢？我們現(xiàn)在再來(lái)分析下如果沒(méi)有缺失數(shù)的話(huà)會(huì)是怎樣呢？假設(shè)所有元素異或得到數(shù)`x2`, 數(shù)`x1`和`x2`有什么差異呢？假設(shè)缺失的數(shù)是`x0`，那么容易知道`x2 = x1 ^ x0`, 相當(dāng)于現(xiàn)在已知`x1`和`x2`，要求`x0`. 根據(jù) [Bit Manipulation](http://algorithm.yuanbin.me/zh-cn/basics_misc/bit_manipulation.html) 中總結(jié)的交換律，`x0 = x1 ^ x2`.
位運(yùn)算的題往往比較靈活，需要好好利用常用等式變換。
### Java
~~~
public class Solution {
/**
* @param nums: an array of integers
* @return: an integer
*/
public int findMissing(int[] nums) {
if (nums == null || nums.length == 0) return -1;
// get xor from 0 to N excluding missing number
int x1 = 0;
for (int i : nums) {
x1 ^= i;
}
// get xor from 0 to N
int x2 = 0;
for (int i = 0; i <= nums.length; i++) {
x2 ^= i;
}
// missing = x1 ^ x2;
return x1 ^ x2;
}
}
~~~
### 源碼分析
略
### 復(fù)雜度分析
遍歷原數(shù)組和 N+1大小的數(shù)組，時(shí)間復(fù)雜度 O(n)O(n)O(n), 空間復(fù)雜度 O(1)O(1)O(1).
### 題解2 - 桶排序
非常簡(jiǎn)單直觀的想法——排序后檢查缺失元素，但是此題中要求時(shí)間復(fù)雜度為 O(n)O(n)O(n), 因此如果一定要用排序來(lái)做，那一定是使用非比較排序如桶排序或者計(jì)數(shù)排序。題中另一提示則是要求只使用 O(1)O(1)O(1) 的額外空間，那么這就是在提示我們應(yīng)該使用原地交換。根據(jù)題意，元素應(yīng)無(wú)重復(fù)，可考慮使用桶排，索引和值一一對(duì)應(yīng)即可。第一重 for 循環(huán)遍歷原數(shù)組，內(nèi)循環(huán)使用 while, 調(diào)整索引處對(duì)應(yīng)的值，直至相等或者索引越界為止，for 循環(huán)結(jié)束時(shí)桶排結(jié)束。最后再遍歷一次數(shù)組找出缺失元素。
初次接觸這種題還是比較難想到使用桶排這種思想的，尤其是利用索引和值一一對(duì)應(yīng)這一特性找出缺失元素，另外此題在實(shí)際實(shí)現(xiàn)時(shí)不容易做到 bug-free, while 循環(huán)處容易出現(xiàn)死循環(huán)。
### Java
~~~
public class Solution {
/**
* @param nums: an array of integers
* @return: an integer
*/
public int findMissing(int[] nums) {
if (nums == null || nums.length == 0) return -1;
bucketSort(nums);
// find missing number
for (int i = 0; i < nums.length; i++) {
if (nums[i] != i) {
return i;
}
}
return nums.length;
}
private void bucketSort(int[] nums) {
for (int i = 0; i < nums.length; i++) {
while (nums[i] != i) {
// ignore nums[i] == nums.length
if (nums[i] == nums.length) {
break;
}
int nextNum = nums[nums[i]];
nums[nums[i]] = nums[i];
nums[i] = nextNum;
}
}
}
}
~~~
### 源碼分析
難點(diǎn)一在于正確實(shí)現(xiàn)桶排，難點(diǎn)二在于數(shù)組元素中最大值 N 如何處理。N 有三種可能：
1. N 不在原數(shù)組中，故最后應(yīng)該返回 N
1. N 在原數(shù)組中，但不在數(shù)組中的最后一個(gè)元素
1. N 在原數(shù)組中且在數(shù)組最后一個(gè)元素
其中情況1在遍歷桶排后的數(shù)組時(shí)無(wú)返回，最后返回 N.
其中2和3在 while 循環(huán)處均會(huì)遇到 break 跳出，即當(dāng)前這個(gè)索引所對(duì)應(yīng)的值要么最后還是 N，要么就是和索引相同的值。如果最后還是 N, 也就意味著原數(shù)組中缺失的是其他值，如果最后被覆蓋掉，那么桶排后的數(shù)組不會(huì)出現(xiàn) N, 且缺失的一定是 N 之前的數(shù)。
綜上，這里的實(shí)現(xiàn)無(wú)論 N 出現(xiàn)在哪個(gè)索引都能正確返回缺失值。實(shí)現(xiàn)上還是比較巧妙的，所以說(shuō)在沒(méi)做過(guò)這類(lèi)題時(shí)要在短時(shí)間內(nèi) bug-free 比較難，當(dāng)然也可能是我比較菜...
另外一個(gè)難點(diǎn)在于如何保證或者證明 while 一定不會(huì)出現(xiàn)死循環(huán)，可以這么理解，如果 while 條件不成立且未出現(xiàn)`nums.length`這個(gè)元素，那么就一定會(huì)使得一個(gè)元素正確入桶，又因?yàn)闆](méi)有重復(fù)元素出現(xiàn)，故一定不會(huì)出現(xiàn)死循環(huán)。
### 復(fù)雜度分析
桶排時(shí)間復(fù)雜度 O(n)O(n)O(n), 空間復(fù)雜度 O(1)O(1)O(1). 遍歷原數(shù)組找缺失數(shù)時(shí)間復(fù)雜度 O(n)O(n)O(n). 故總的時(shí)間復(fù)雜度為 O(n)O(n)O(n), 空間復(fù)雜度 O(1)O(1)O(1).
- Preface
- Part I - Basics
- Basics Data Structure
- String
- Linked List
- Binary Tree
- Huffman Compression
- Queue
- Heap
- Stack
- Set
- Map
- Graph
- Basics Sorting
- Bubble Sort
- Selection Sort
- Insertion Sort
- Merge Sort
- Quick Sort
- Heap Sort
- Bucket Sort
- Counting Sort
- Radix Sort
- Basics Algorithm
- Divide and Conquer
- Binary Search
- Math
- Greatest Common Divisor
- Prime
- Knapsack
- Probability
- Shuffle
- Basics Misc
- Bit Manipulation
- Part II - Coding
- String
- strStr
- Two Strings Are Anagrams
- Compare Strings
- Anagrams
- Longest Common Substring
- Rotate String
- Reverse Words in a String
- Valid Palindrome
- Longest Palindromic Substring
- Space Replacement
- Wildcard Matching
- Length of Last Word
- Count and Say
- Integer Array
- Remove Element
- Zero Sum Subarray
- Subarray Sum K
- Subarray Sum Closest
- Recover Rotated Sorted Array
- Product of Array Exclude Itself
- Partition Array
- First Missing Positive
- 2 Sum
- 3 Sum
- 3 Sum Closest
- Remove Duplicates from Sorted Array
- Remove Duplicates from Sorted Array II
- Merge Sorted Array
- Merge Sorted Array II
- Median
- Partition Array by Odd and Even
- Kth Largest Element
- Binary Search
- Binary Search
- Search Insert Position
- Search for a Range
- First Bad Version
- Search a 2D Matrix
- Search a 2D Matrix II
- Find Peak Element
- Search in Rotated Sorted Array
- Search in Rotated Sorted Array II
- Find Minimum in Rotated Sorted Array
- Find Minimum in Rotated Sorted Array II
- Median of two Sorted Arrays
- Sqrt x
- Wood Cut
- Math and Bit Manipulation
- Single Number
- Single Number II
- Single Number III
- O1 Check Power of 2
- Convert Integer A to Integer B
- Factorial Trailing Zeroes
- Unique Binary Search Trees
- Update Bits
- Fast Power
- Hash Function
- Count 1 in Binary
- Fibonacci
- A plus B Problem
- Print Numbers by Recursion
- Majority Number
- Majority Number II
- Majority Number III
- Digit Counts
- Ugly Number
- Plus One
- Linked List
- Remove Duplicates from Sorted List
- Remove Duplicates from Sorted List II
- Remove Duplicates from Unsorted List
- Partition List
- Two Lists Sum
- Two Lists Sum Advanced
- Remove Nth Node From End of List
- Linked List Cycle
- Linked List Cycle II
- Reverse Linked List
- Reverse Linked List II
- Merge Two Sorted Lists
- Merge k Sorted Lists
- Reorder List
- Copy List with Random Pointer
- Sort List
- Insertion Sort List
- Check if a singly linked list is palindrome
- Delete Node in the Middle of Singly Linked List
- Rotate List
- Swap Nodes in Pairs
- Remove Linked List Elements
- Binary Tree
- Binary Tree Preorder Traversal
- Binary Tree Inorder Traversal
- Binary Tree Postorder Traversal
- Binary Tree Level Order Traversal
- Binary Tree Level Order Traversal II
- Maximum Depth of Binary Tree
- Balanced Binary Tree
- Binary Tree Maximum Path Sum
- Lowest Common Ancestor
- Invert Binary Tree
- Diameter of a Binary Tree
- Construct Binary Tree from Preorder and Inorder Traversal
- Construct Binary Tree from Inorder and Postorder Traversal
- Subtree
- Binary Tree Zigzag Level Order Traversal
- Binary Tree Serialization
- Binary Search Tree
- Insert Node in a Binary Search Tree
- Validate Binary Search Tree
- Search Range in Binary Search Tree
- Convert Sorted Array to Binary Search Tree
- Convert Sorted List to Binary Search Tree
- Binary Search Tree Iterator
- Exhaustive Search
- Subsets
- Unique Subsets
- Permutations
- Unique Permutations
- Next Permutation
- Previous Permuation
- Unique Binary Search Trees II
- Permutation Index
- Permutation Index II
- Permutation Sequence
- Palindrome Partitioning
- Combinations
- Combination Sum
- Combination Sum II
- Minimum Depth of Binary Tree
- Word Search
- Dynamic Programming
- Triangle
- Backpack
- Backpack II
- Minimum Path Sum
- Unique Paths
- Unique Paths II
- Climbing Stairs
- Jump Game
- Word Break
- Longest Increasing Subsequence
- Palindrome Partitioning II
- Longest Common Subsequence
- Edit Distance
- Jump Game II
- Best Time to Buy and Sell Stock
- Best Time to Buy and Sell Stock II
- Best Time to Buy and Sell Stock III
- Best Time to Buy and Sell Stock IV
- Distinct Subsequences
- Interleaving String
- Maximum Subarray
- Maximum Subarray II
- Longest Increasing Continuous subsequence
- Longest Increasing Continuous subsequence II
- Graph
- Find the Connected Component in the Undirected Graph
- Route Between Two Nodes in Graph
- Topological Sorting
- Word Ladder
- Bipartial Graph Part I
- Data Structure
- Implement Queue by Two Stacks
- Min Stack
- Sliding Window Maximum
- Longest Words
- Heapify
- Problem Misc
- Nuts and Bolts Problem
- String to Integer
- Insert Interval
- Merge Intervals
- Minimum Subarray
- Matrix Zigzag Traversal
- Valid Sudoku
- Add Binary
- Reverse Integer
- Gray Code
- Find the Missing Number
- Minimum Window Substring
- Continuous Subarray Sum
- Continuous Subarray Sum II
- Longest Consecutive Sequence
- Part III - Contest
- Google APAC
- APAC 2015 Round B
- Problem A. Password Attacker
- Microsoft
- Microsoft 2015 April
- Problem A. Magic Box
- Problem B. Professor Q's Software
- Problem C. Islands Travel
- Problem D. Recruitment
- Microsoft 2015 April 2
- Problem A. Lucky Substrings
- Problem B. Numeric Keypad
- Problem C. Spring Outing
- Microsoft 2015 September 2
- Problem A. Farthest Point
- Appendix I Interview and Resume
- Interview
- Resume