思路
要求小于O(n^2)的复杂度，又不能修改，目测就是O(nlogn)的复杂度，所以想到可能是用二分搜索。但是数组是无序的，所以无法对数组进行二分搜索。因为找重复数是有范围的[1, n],所以我们可以看看是否可以在这个范围里进行二分查找。如果有重复数x， 则小于x的mid的 cnt 都是小于或等于mid的，cnt指小于或等于这个数字的个数。
代码
//
// main.cpp
// leetcode
//
// Created by YangKi on 15/11/19.
// Copyright © 2015年 YangKi. All rights reserved.
#include<vector>
#include<algorithm>
#include<cstdio>
#include <unordered_map>
#include <unordered_set>
#include <cmath>
#include <string>
#include <set>
#include <cstdlib>
using namespace std;
class Solution {
private:
int count(vector<int>& nums, int mid)
{
int cnt = 0;
for (vector<int>::iterator it = nums.begin(); it != nums.end(); it++)
{
if (*it <= mid)
{
cnt++;
}
}
return cnt;
}
public:
int findDuplicate(vector<int>& nums)
{
// !!!!!!!!!!!!!!!!!!!!!!!!! 前提是数组已经排序
int size = (int)nums.size();
int low = 1;
int high = size - 1;
int mid = 0;
while (low < high)
{
mid = low + (high - low)/2;
int cnt = count(nums, mid);
if (cnt <= mid)
{
// 这个范围内不会有答案，所以直接往后
low = mid + 1;
}
else
{ // cnt > mid， 有可能包含答案，所以依旧包含
high = mid;
}
}
return low;
}
};
