【3】一维数组中查找是否含有重复的数字

系统管理员 2022-05-27 05:41 200阅读 0赞

## 面试三： 数组中的重复数字 ##

**题目：**在一个长为N+的数组里，所有数字都在1~n的范围内，  
所以数组中至少有一个数字是重复的，请找出数组中任意一个重复的数字，  
但是不能修改数组；  
例如： 如果输入的长度为8的数组\{2,1,5,4,3,2,6,7\}，那么对应的输出是重复的数字2或者3  
**分析 ：**利用二分查找法，将1~n的数字从中间一分为二，前半部分1~m，后半部分m+1~n，如果1~m的数字超过m，那么，这半部分一定包含重复数字，在对1~m进行二分，以此内推；  
**代码如下：**

#include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    
    int CountRange(const int* string,int length,int start,int end)
    {
        if(string == NULL)
            return 0;
        int count = 0;
        for(int i = 0;i< length;i++)
        {
            if(string[i] >= start&&string[i]<= end)
            {
                ++count;
            }
        }
        return count;
    }
    
    int getDuplication(const int*  string,int length)
    {
        if(string == NULL || length <= 0)
        {
            printf("参数传递错误\n");
            return  2;
        }
        int start = 1;
        int end = length -1;
        while(end >= start)
        {
            int mid = ( (end - start)>>1 )+ start;
            int count  = CountRange(string,length, start,mid);
            if(end == start)
            {
                if(count >1 )
                return start;
                else
                    break;
            }
            if(count > (mid - start)+1)
                end = mid;
            else start = mid + 1;
        }
        return -1;
    }
    
    //====================测试代码=================
    //*********************************************
    //=============================================
    void test(int buf[],int len)
    {
        printf("该数组大小为： %d\n",len);
        int ret = getDuplication(buf,len);
    
        if(ret == -1)
        {
            printf("该数组中无重复数字\n");
        }
        else{
            if(ret == 2)
            {
                return;
            }
            printf("重复数字为:%d\n",ret);
        }
    }
    //========数组中存在重复数字==========================
    void test1()
    {
        int buf[8] = {
       2,1,5,4,3,2,6,7};
        int len = sizeof(buf)/sizeof(buf[0]);
        test( buf,len);
    }
    //================数组中不存在重复数字=================
    void test2()
    {
        int buf[10] = {
       0,8,5,4,9,2,6,1,7,3};
        int len = sizeof(buf)/sizeof(buf[0]);
        test( buf,len);
    }
    
    //==============测试代码的鲁棒性======================
    void test3()
    {
        int buf[10] ;
        int *p = NULL;
        int len = sizeof(p);
        test(p,len);
    }
    int main()
    {
        test1();
        test2();
        test3();
        return 0;
    }

**结果展示：**   
![70][]

[70]: /images/20220527/6bffbd5e9ff84384b15a6927953ccbf5.png