problem:
Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.
Note:
O(n2).Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.
Subscribe to see which companies asked this question
1 class Solution { 2 public: 3 int findDuplicate(vector<int>& nums) { 4 //二分查找法的运用 5 6 int low=0,high=nums.size()-1; 7 8 9 while(low<=high) 10 { 11 int cnt=0; 12 int middle=low+(high-low)/2; 13 14 for(int i=0;i<nums.size();i++) 15 { 16 if(nums[i]<=middle) 17 cnt++; 18 } 19 20 if(cnt>middle) 21 high=middle-1; 22 else 23 low=middle+1; 24 } 25 26 return low; 27 28 29 } 30 };
LeetCode: Find the Duplicate Number
原文：http://www.cnblogs.com/xiaoying1245970347/p/5224968.html