温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

不修改数组找出重复的数字(c语言)

发布时间:2020-07-24 01:11:51 来源:网络 阅读:769 作者:梦T醒 栏目:编程语言

不修改数组找出重复的数字(c语言)让人瑟瑟发抖的面试题


不修改数组找出重复的数字(c语言)来我们看一下题目
在一个 长度为n+1的数组里的所有数字都在1~n的范围内,所以数组中至少有一个数字是重复的。请找出数组中任意一个重复的数字,但不能修改输入的数组。
注意:时间复杂度O(n),空间复杂度O(1)

不修改数组找出重复的数字(c语言)找出数组中重复的数字(c语言)怎么解决勒???
分析:利用题目中元素处于1~n的范围,把元素分为两组,判断两组元素个数,如果大于范围,则重复的数字就在这个范围内。例如:1~3范围中有4个数,说明其中至少有一个重复的数字。按此二分下去,将会剩下一个数字有两个,最后输出。
不修改数组找出重复的数字(c语言)来看看代码

#include<stdio.h>
#define SIZE(arr) sizeof(arr)/sizeof(arr[0])//数组长度

int count_r(const int *arr,int start, int end,int len)//元素范围内元素的个数
{
    int count = 0;
    int i = 0;
    for (; i < len; i++)
    {
        if (arr[i] >= start&&arr[i] <= end)
        {
            count++;
        }
    }
    return count;
}
int duplicate1(const int *arr, int len)
{
    if (len < 0)
    {
        return 0;
    }
    int start = 1, end = len - 1;
    int count = 0;
    while (end >= start)
    {
        int mid = ((end - start) >> 1) + start;//元素中值
        count = count_r(arr,start, mid,len);//元素二分后,其中一组元素范围的个数
        if (count>(mid - start + 1))//确定元素范围
        {
            end = mid;
        }
        else
        {
            start = mid+1;
        }
        if (end == start)//确定元素定位到一个元素
        {
            if (count > 1)
                return start;
            else
                break;
        }
    }
    return 0;
}
int main()
{
    int arr[] = { 2, 3, 5,4,3,2,6,7 };
    printf("%d", duplicate1(arr, SIZE(arr)));
    return 0;
}

不修改数组找出重复的数字(c语言)总结:在不修改数组的情况下,只要知道数组元素范围,就可以通过二分元素的方法,找到重复的数字

向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

AI