不修改數(shù)組找出重復(fù)的數(shù)字（c語(yǔ)言）-創(chuàng)新互聯(lián)

讓人瑟瑟發(fā)抖的面試題
。
。
。

創(chuàng)新互聯(lián)專(zhuān)業(yè)IDC數(shù)據(jù)服務(wù)器托管提供商，專(zhuān)業(yè)提供成都服務(wù)器托管，服務(wù)器租用，成都服務(wù)器托管，成都服務(wù)器托管，成都多線服務(wù)器托管等服務(wù)器托管服務(wù)。

來(lái)我們看一下題目
在一個(gè) 長(zhǎng)度為n+1的數(shù)組里的所有數(shù)字都在1~n的范圍內(nèi)，所以數(shù)組中至少有一個(gè)數(shù)字是重復(fù)的。請(qǐng)找出數(shù)組中任意一個(gè)重復(fù)的數(shù)字，但不能修改輸入的數(shù)組。
注意：時(shí)間復(fù)雜度O（n），空間復(fù)雜度O(1)

找出數(shù)組中重復(fù)的數(shù)字（c語(yǔ)言）怎么解決勒？？？
分析：利用題目中元素處于1~n的范圍，把元素分為兩組，判斷兩組元素個(gè)數(shù)，如果大于范圍，則重復(fù)的數(shù)字就在這個(gè)范圍內(nèi)。例如：1~3范圍中有4個(gè)數(shù)，說(shuō)明其中至少有一個(gè)重復(fù)的數(shù)字。按此二分下去，將會(huì)剩下一個(gè)數(shù)字有兩個(gè)，最后輸出。
來(lái)看看代碼

#include<stdio.h>
#define SIZE(arr) sizeof(arr)/sizeof(arr[0])//數(shù)組長(zhǎng)度

int count_r(const int *arr,int start, int end,int len)//元素范圍內(nèi)元素的個(gè)數(shù)
{
    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);//元素二分后，其中一組元素范圍的個(gè)數(shù)
        if (count>(mid - start + 1))//確定元素范圍
        {
            end = mid;
        }
        else
        {
            start = mid+1;
        }
        if (end == start)//確定元素定位到一個(gè)元素
        {
            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;
}

總結(jié)：在不修改數(shù)組的情況下，只要知道數(shù)組元素范圍，就可以通過(guò)二分元素的方法，找到重復(fù)的數(shù)字

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無(wú)理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國(guó)服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡(jiǎn)單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專(zhuān)為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場(chǎng)景需求。

分享題目：不修改數(shù)組找出重復(fù)的數(shù)字（c語(yǔ)言）-創(chuàng)新互聯(lián)
URL地址：http://bm7419.com/article14/gegde.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站收錄、移動(dòng)網(wǎng)站建設(shè)、靜態(tài)網(wǎng)站、響應(yīng)式網(wǎng)站、定制網(wǎng)站、手機(jī)網(wǎng)站建設(shè)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)