Catch the sparkle: if only one number is duplicated in [1..n], all following numbers will be "shifted" right.
class Solution { public: int findDuplicate(vector<int>& nums) { int np = nums.size(); int n = np - 1; int s = 1, e = n; while(s<e) { int mid = (s + e) / 2; int cnt = 0; for(auto v : nums) if(v <= mid) cnt++; if(cnt >mid) { e = mid; } else { s= mid + 1; } } return s; } };
And yes, there is a smarter solution: http://keithschwarz.com/interesting/code/?dir=find-duplicate
LeetCode "Find the Duplicate Number"
原文：http://www.cnblogs.com/tonix/p/4847633.html