287. Find the Duplicate Number

My intuition is to brute force finding the duplicated number. The running time will be O(n*n). However, the problem require us to solve it by less O(n*n). To solve the problem, we need to know Pigeonhole Principle, i.e., if m items are put into n containers with m > n, then at least one container must contain more than one items. This problem is a special case with m = n+1. Applying Pigeonhole Principle to this problem, if there are larger than k numbers in the array, then the duplicate must be in [0, k] and the value of duplicate number will be in [0, k] because the number of container is only one more than the maximum number. If we calculate k by binary search, we can solve this problem by O(n*logn).

1:  class Solution {  
2:  public:  
3:    int findDuplicate(vector<int>& nums) {  
4:      int lo = 0, hi = nums.size()-1;  
5:      while (lo <= hi) {  
6:        int mid = lo + (hi - lo) / 2;  
7:        int cnt = 0;  
8:        for (int n : nums) {  
9:          if (n <= mid) cnt++;  
10:        }  
11:        if (cnt > mid) hi = mid-1;  
12:        else lo = mid + 1;  
13:      }  
14:      return lo;  
15:    }  
16:  };