劍指offer之不修改數(shù)組找出重復(fù)的數(shù)字

1  題目
 
不修改數(shù)組找出重復(fù)的數(shù)字

在一個長度為N+1的數(shù)組里面的所有數(shù)字都在范圍1~N范圍內(nèi)，所以數(shù)組至少
有一個數(shù)字是重復(fù)的，請找出重復(fù)數(shù)字，但是不能修改輸入的數(shù)組。

2  思路

思路1：

我們開辟一個新的數(shù)組，初始化為0，然后把原始數(shù)組每個數(shù)據(jù)的值作為下標(biāo)，把新數(shù)組通過這個下標(biāo)數(shù)據(jù)取出來，如果取出來是1，就說明這個下標(biāo)數(shù)據(jù)重復(fù)了，如果不是，我們直接放進(jìn)去，然后進(jìn)行新數(shù)組值進(jìn)行++操作。

 
思路2:

比如數(shù)據(jù)1 2 2 3 4 5 6 7， 我們先找到中間的值(1 + 7) / 2 = 4;然后我們判斷數(shù)組里面每個元素 1到4有多少個，如果有大于4個數(shù)的話，我們一定說明重復(fù)數(shù)據(jù)在范圍1到4里面，反之在范圍4到7中，比如我們上面的數(shù)據(jù)1到4有5個數(shù)據(jù)，我們說明可以知道重復(fù)數(shù)據(jù)范圍是1到4，然后我們再把數(shù)據(jù)切一刀，從1到4， 有點(diǎn)像二分法，以此類推，知道我們求出答案。

關(guān)鍵點(diǎn)：

1）我們要個輔助函數(shù)：需要知道數(shù)組中從范圍start到end的元素個數(shù)

2）循環(huán)條件是while(end >= start)

3)  退循環(huán)條件是在while里面，if(end == start) {通過輔助函數(shù)得到的個數(shù)大于1就返回這個start值} else {break;}
 
 
3  代碼實(shí)現(xiàn)

    #include <iostream>
     
    using namespace std;
     
    int getCount(const int *a, int len, int start, int end)
    {
        if (a == NULL || len <= 0)
        {
            return 0;
        }
        int count = 0;
        for (int i = 0; i < len; ++i)
        {
            if (a[i] >= start && a[i] <= end)
            {
                ++count;
            }
        }
        return count;
    }
     
    int getResetNumber(const int *a, int len)
    {
        if (a == NULL || len <= 0)
        {
            return -1;
        }
        int start = 1, end = len - 1;
        //int mid = (end - start) / 2 + start;
        while (end >= start)
        {
            int mid = (end - start) / 2 + start;
            int count = getCount(a, len, 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;
    }
     
     
    int main()
    {
        std::cout << "請輸入數(shù)組的長度" << std::endl;
        int len = 0;
        std::cin >> len;
        if (len <= 0)
        {
            std::cout << "數(shù)組的長度不合法" << std::endl;
            return -1;
        }
        int *a = new int[len];
        std::cout << "請分別輸入數(shù)組的每個數(shù)據(jù)" << std::endl;
        for (int i = 0; i < len; ++i)
        {
            std::cin >> a[i];
            if (a[i] <= 0 || a[i] >= len)
            {
                std::cout << "輸入的數(shù)據(jù)有誤" << std::endl;
                return -1;
            }
        }
        //int count = getCount(a, len, 1, len - 1);
        int value = getResetNumber(a, len);
        if (value == -1)
        {
            std::cout << "沒有找到重復(fù)的數(shù)據(jù)" << std::endl;
            return -1;
        }
        std::cout << "其中一個重復(fù)的數(shù)據(jù)是" << value << std::endl;
        delete []a;
        return 0;
    }
                                                                                                                                                         89,1          Bot

 
4  運(yùn)行結(jié)果

    請輸入數(shù)組的長度
    5
    請分別輸入數(shù)組的每個數(shù)據(jù)
    1
    2
    3
    4
    2
    其中一個重復(fù)的數(shù)據(jù)是2

 
5  本質(zhì)和總結(jié)

 在區(qū)間start~end里面，我們要縮小一半?yún)^(qū)間，我們直接找到start~end的中間數(shù)M = (start - end) / 2 + start，然后遍歷數(shù)組，如果在這個范圍的數(shù)據(jù)等于M 大于(M - start + 1)說明這個段區(qū)間有重復(fù)數(shù)據(jù)，反之?dāng)?shù)目重復(fù)數(shù)據(jù)在M+1到end區(qū)間，然后每次這切割，以此類推，所以這里要用到循環(huán)，用循環(huán)就要條件，我們知道二分法這些操作條件是while(end >= start),既然有循環(huán)，那我們必須找到跳出循環(huán)條件的條件在while循環(huán)里面 if (end == start) {輔助函數(shù)個數(shù) > 1} else {break;}
 


 


作者：chen.yu
深信服三年半工作經(jīng)驗(yàn)，目前就職游戲廠商，希望能和大家交流和學(xué)習(xí),
微信公眾號：編程入門到禿頭 或掃描下面二維碼
零基礎(chǔ)入門進(jìn)階人工智能(鏈接)