剑指offer_数组中重复的数字

找出数组中重复的数字

1、题目一：找出数组中重复的数字

在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是重复的数字2或者3。

• 思路1：先排序再找重复数组，排序一个长度为n的数组需要O(nlogn)的时间。
• 思路2：数组中的数字都在0~n-1范围内，如果这个数组中没有重复的数字，那么对应的下标 i 和 它位置上的值是一致的。
  • 从头到尾扫描这个数组中的每个数字，假设数组为a数组，下标为i，则比较 i 和 a[i] 的值，若一致，就扫描下一个。若不一致，则比较当前值和下标为a[i] 的值，若一致，则找到了，若不一致，则交换a[i] 和 a[a[i]]。

#include<cstdio>
#include<iostream>
#define nullptr 0
using namespace std;
bool duplicate(int numbers[],int length,int* duplication){
    if(numbers==nullptr || length <= 0){
        return false;
    }
    for(int i=0;i<length;i++){
        if(numbers[i]<0||numbers[i]>length-1)
            return false;
    }
    for(int i=0;i<length;i++){
        while(numbers[i]!=i){
            if(numbers[i]==numbers[numbers[i]]){
                *duplication=numbers[i];
                return true;
            }
            int temp = numbers[i];
            numbers[i]=numbers[temp];
            numbers[temp]=temp;
        }
    }
    return false;
}
int main(){
    int numbers[] = {2, 4, 2, 1, 4 };
    int duplications[] = { 2,4 };
    cout<<duplicate(numbers,5,duplications)<<endl;//输出1 
    return 0;
}

2、题目二：找出数组中重复的数字，不改变原数组

不修改数组的条件下，找出数组中重复的数字；其中数组长度为n+1，数组值的范围1~n；

• 思路：如果1~n没有重复的数字，则会有n个数字，数组长度为n+1，则一定会有重复数字。利用二分的思想，判断在每个范围内的数字有多少个就可以判断哪个数字重复了。

#include<iostream> 
using namespace std;
#define nullptr 0
int countRange(int numbers[],int length,int start,int end);

//返回正数：输入有效且存在重复数字，返回为重复的数字
//返回负数：输入无效或者数组中没有重复的数字
int getDuplication(int numbers[],int length){
    if(numbers==nullptr || length<=0){
        return -1;
    }
    int start =1;
    int end = length-1;
    while(end>=start){
        int middle = ((end-start)/2)+start;
        int count=countRange(numbers,length,start,middle);
        if(end==start){
            if(count>1) return start;
            break;
        }
        if(count>(middle-start+1)){
            end=middle; 
        }
        else
            start=middle+1;
    }
    return -1;
} 
int countRange(int numbers[], int length, int start, int end)
{
    if(numbers == nullptr)
        return 0;

    int count = 0;
    for(int i = 0; i < length; i++)
        if(numbers[i] >= start && numbers[i] <= end)
            ++count;
    return count;
}

int main(){
    int numbers[] = { 2, 3, 5, 4, 3, 2, 6, 7 };
    cout<<getDuplication(numbers,8);
    return 0;
}