思路

要求小于O(n^2)的復(fù)雜度，又不能修改，目測就是O(nlogn)的復(fù)雜度，所以想到可能是用二分搜索。但是數(shù)組是無序的，所以無法對數(shù)組進行二分搜索。因為找重復(fù)數(shù)是有范圍的[1, n],所以我們可以看看是否可以在這個范圍里進行二分查找。如果有重復(fù)數(shù)x， 則小于x的mid的 cnt 都是小于或等于mid的，cnt指小于或等于這個數(shù)字的個數(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)
            {
                //  這個范圍內(nèi)不會有答案，所以直接往后
                low = mid + 1;
            }
            else
            { // cnt > mid， 有可能包含答案，所以依舊包含
                high = mid;
            }
        }
        
        return low;
        
    }
};