1 題目
不修改數組找出重復的數字
在一個長度為N+1的數組里面的所有數字都在范圍1~N范圍內，所以數組至少有一個數字是重復的，請找出重復數字，但是不能修改輸入的數組。
2 思路
思路1：
我們開辟一個新的數組，初始化為0，然后把原始數組每個數據的值作為下標，把新數組通過這個下標數據取出來，如果取出來是1，就說明這個下標數據重復了，如果不是，我們直接放進去，然后進行新數組值進行++操作。
思路2:
比如數據1 2 2 3 4 5 6 7， 我們先找到中間的值(1 + 7) / 2 = 4;然后我們判斷數組里面每個元素 1到4有多少個，如果有大于4個數的話，我們一定說明重復數據在范圍1到4里面，反之在范圍4到7中，比如我們上面的數據1到4有5個數據，我們說明可以知道重復數據范圍是1到4，然后我們再把數據切一刀，從1到4， 有點像二分法，以此類推，知道我們求出答案。
關鍵點：
1）我們要個輔助函數：需要知道數組中從范圍start到end的元素個數
2）循環條件是while(end >= start)
3) 退循環條件是在while里面，if(end == start) {通過輔助函數得到的個數大于1就返回這個start值} else {break;}
3 代碼實現
#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 << "請輸入數組的長度" << std::endl; int len = 0; std::cin >> len; if (len <= 0) { std::cout << "數組的長度不合法" << std::endl; return -1; } int *a = new int[len]; std::cout << "請分別輸入數組的每個數據" << std::endl; for (int i = 0; i < len; ++i) { std::cin >> a[i]; if (a[i] <= 0 || a[i] >= len) { std::cout << "輸入的數據有誤" << std::endl; return -1; } } //int count = getCount(a, len, 1, len - 1); int value = getResetNumber(a, len); if (value == -1) { std::cout << "沒有找到重復的數據" << std::endl; return -1; } std::cout << "其中一個重復的數據是" << value << std::endl; delete []a; return 0;}4 運行結果
請輸入數組的長度
5
請分別輸入數組的每個數據
1
2
3
4
2
其中一個重復的數據是2
5 本質和總結
在區間start~end里面，我們要縮小一半區間，我們直接找到start~end的中間數M = (start - end) / 2 + start，然后遍歷數組，如果在這個范圍的數據等于M 大于(M - start + 1)說明這個段區間有重復數據，反之數目重復數據在M+1到end區間，然后每次這切割，以此類推，所以這里要用到循環，用循環就要條件，我們知道二分法這些操作條件是while(end >= start),既然有循環，那我們必須找到跳出循環條件的條件在while循環里面 if (end == start) {輔助函數個數 > 1} else {break;}
以上就是這篇文章的全部內容了，希望本文的內容對大家的學習或者工作具有一定的參考學習價值，謝謝大家對武林網的支持。如果你想了解更多相關內容請查看下面相關鏈接
新聞熱點
疑難解答
圖片精選
