溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
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;}
以上就是這篇文章的全部內容了，希望本文的內容對大家的學習或者工作具有一定的參考學習價值，謝謝大家對億速云的支持。如果你想了解更多相關內容請查看下面相關鏈接
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
