面试题4:找到数组中重复的数字[不修改数组]

1.

在一个长度为n+1的数组中所有数字都在1~n的范围内,所以数组中至少有一个数字是重复的。请找出数组中任意一个重复的数字,但是不能改变输入的数组。例如:数组长度为8的数组{2,3,5,4,3,2,6,7},则重复的数字就是2或者3

2.思路

注意不允许修改原数组,则pass排序、交换这两种方法。
(1)hash 时间复杂度:O(1) , 额外空间复杂度:O(n)
(2)二分 时间复杂度:O(nlogn),额外空间复杂度:O(1) 【以mid作为划分值,统计此范围内数的个数,如果大于mid-st+1,则该区域肯定会有重复的数字,否则另外一半存在】

3.code

#include <iostream>
#include <string>
#include <string.h>
using namespace std;

int find_by_hash(const int arr[], int len)
{
    if(arr == NULL || len <= 0) return -1;
    int hash[len];
    int res = -1;
    for(int i = 0; i < len; ++i){
        hash[arr[i]]++;
        if(hash[arr[i]] > 1){
            res = arr[i];
            break;
        }
    }
    return res;
}

//二分,
int range_count(const int arr[], int len, int st, int ed){
    if(arr == NULL || len <= 0){
        return 0;
    }
    int count = 0;
    for(int i = 0; i < len; ++i){
        if(arr[i] >= st && arr[i] <= ed){
            count++;
        }
    }
    return count;
}

int find_by_bin(const int arr[], int len)
{
    if(arr == NULL ||len <= 0) return -1;
    int st = 1;
    int ed = len-1;
    while(st <= ed){
        int mid = st + (ed - st) / 2;
        int count = range_count(arr,len,st,mid);
        if(st == ed){
            if(count > 1)
                return st;
            else
                break;
        }
        if(count > (mid-st+1)){
            ed = mid;
        }else{
            st = mid+1;
        }
    }
    return -1;
}

int main()
{
    int arr[] = {2,3,6,7,5,3,2,4};
    int len = sizeof(arr)/sizeof(arr[0]);

    cout <<"init arr:" << endl;
    for(int i = 0; i < len; ++i){
        cout << arr[i] << " ";
    }
    cout<<"\n";
    int res1,res2;
    res1 = find_by_hash(arr,len);
    res2 = find_by_bin(arr,len);
    cout << "res1: " << res1 << endl;
    cout << "res2: " << res2 << endl;
    cout <<"after find arr:" << endl;
    for(int i = 0; i < len; ++i){
        cout << arr[i] << " ";
    }
    return 0;
}

4.结果截图

图片说明