思路
要求小于O(n^2)的復(fù)雜度打却，又不能修改捌肴，目測(cè)就是O(nlogn)的復(fù)雜度，所以想到可能是用二分搜索饥悴。但是數(shù)組是無(wú)序的，所以無(wú)法對(duì)數(shù)組進(jìn)行二分搜索。因?yàn)檎抑貜?fù)數(shù)是有范圍的[1, n],所以我們可以看看是否可以在這個(gè)范圍里進(jìn)行二分查找擒滑。如果有重復(fù)數(shù)x， 則小于x的mid的 cnt 都是小于或等于mid的巨柒，cnt指小于或等于這個(gè)數(shù)字的個(gè)數(shù)珍坊。
代碼
//
// 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)
{
// !!!!!!!!!!!!!!!!!!!!!!!!! 前提是數(shù)組已經(jīng)排序
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)
{
// 這個(gè)范圍內(nèi)不會(huì)有答案回还，所以直接往后
low = mid + 1;
}
else
{ // cnt > mid蝗柔， 有可能包含答案洪灯，所以依舊包含
high = mid;
}
}
return low;
}
};
