我一直在嘗試解決以下問題：
給定一個n 1整數陣列，其中所有元素都位于[1,n]. 您還知道其中一個元素重復了一定次數，而其他元素是不同的。開發一種演算法來查找重復的數字和重復的次數。
這是我的解決方案，我讓 k = 重復數：
struct LatticePoint{ // to hold duplicate and k
int a;
int b;
LatticePoint(int a_, int b_) : a(a_), b(b_) {}
}
LatticePoint findDuplicateAndK(const std::vector<int>& A){
int n = A.size() - 1;
std::vector<int> Numbers (n);
for(int i = 0; i < n 1; i){
Numbers[A[i] - 1]; // A[i] in range [1,n] so no out-of-access
}
int i = 0;
while(i < n){
if(Numbers[i] > 1) {
int duplicate = i 1;
int k = Numbers[i] - 1;
LatticePoint result{duplicate, k};
return LatticePoint;
}
所以，基本思想是這樣的：我們沿著陣列前進，每次看到數字時，A[i]我們都會增加 的值Numbers[A[i]]。由于只有重復出現不止一次，所以數值大于1的Numbers條目的索引必須是條目的值為重復數-1的重復數。這種演算法O(n)在時間復雜度和O(n)空間上都有。
我想知道是否有人有一個在時間和/或空間上更好的解決方案？（或者實際上，如果我的解決方案中有任何錯誤......）
uj5u.com熱心網友回復：
您的代碼的想法有效。
但是，多虧了這些n 1元素，我們可以實作其他時間和空間的權衡。
如果我們有一定數量的桶，我們要在它們之間劃分數字，把n 1數字放進去意味著一些桶必須比預期的要多。這是眾所周知的鴿巢原理的變體。
所以我們使用 2 個桶，一個用于范圍1..floor(n/2)，一個用于floor(n/2) 1..n. 一次通過陣列后，我們知道答案在哪一半。然后我們將那一半分成兩半，再通過一次，依此類推。這將導致二進制搜索，它將通過O(1)資料獲得答案，并with ceil(log_2(n))通過，每次都需要 time O(n)。因此我們及時得到了答案O(n log(n))。
現在我們不需要使用 2 個桶。如果我們使用 3，我們會ceil(log_3(n))通過。因此，當我們增加固定數量的桶時，我們會占用更多空間并節省時間。還有其他權衡嗎？
好吧，您展示了如何使用n水桶在 1 次通過中做到這一點。您需要在 2 次通過中完成多少個桶？事實證明，答案至少是sqrt(n)buckekts。立方根可以進行 3 次傳遞。等等。
因此，您需要進行一系列權衡，您擁有的存盤桶越多，需要的空間就越多，但通過的次數就越少。而您的解決方案只是在極端情況下，占用最多的空間和最少的時間。
uj5u.com熱心網友回復：
您可以將暫存空間減少到位n而不是n ints，前提是您已經或愿意撰寫bitset具有運行時指定大小的 a（請參閱 參考資料boost::dynamic_bitset）。
在您知道哪個元素重復之前，您不需要收集重復計數，然后您只需要保留該計數。因此，您需要跟蹤的只是您之前是否看到過該值（因此是n位）。找到重復值后，設定count為 2 并遍歷向量的其余部分，count每次點擊該值的實體時遞增。（您初始化count為 2，因為當您到達那里時，您將看到其中的兩個。）
那仍然是 O(n) 空間，但常數因子要小得多。
uj5u.com熱心網友回復：
這是一個更厚臉皮的演算法，它只需要恒定的空間，但會重新排列輸入向量。（它只是重新排序；所有原始元素仍然存在于最后。）
它仍然是 O(n) 時間，盡管這可能并不完全明顯。這個想法是嘗試重新排列陣列，使 A[i] 為 i，直到我們找到重復項。當我們嘗試將一個元素放在正確的索引處時，重復項將出現，事實證明該索引已經包含該元素。這樣，我們就找到了重復項；我們有一個想要移動到 A[j] 的值，但相同的值已經在 A[j] 處。然后我們掃描陣列的其余部分，每次找到另一個實體時遞增計數。
#include <utility>
#include <vector>
std::pair<int, int> count_dup(std::vector<int> A) {
/* Try to put each element in its "home" position (that is,
* where the value is the same as the index). Since the
* values start at 1, A[0] isn't home to anyone, so we start
* the loop at 1.
*/
int n = A.size();
for (int i = 1; i < n; i) {
while (A[i] != i) {
int j = A[i];
if (A[j] == j) {
/* j is the duplicate. Now we need to count them.
* We have one at i. There's one at j, too, but we only
* need to add it if we're not going to run into it in
* the scan. And there might be one at position 0. After that,
* we just scan through the rest of the array.
*/
int count = 1;
if (A[0] == j) count;
if (j < i) count;
for ( i; i < n; i) {
if (A[i] == j) count;
}
return std::make_pair(j, count);
}
/* This swap can only happen once per element. */
std::swap(A[i], A[j]);
}
}
/* If we get here, every element from 1 to n is at home.
* So the duplicate must be A[0], and the duplicate count
* must be 2.
*/
return std::make_pair(A[0], 2);
}
uj5u.com熱心網友回復：
具有 O(1) 復雜度的并行解決方案是可能的。
引入一個原子布爾陣列和兩個原子整數，稱為重復和計數。首先將 count 設定為 1。然后在數字的索引位置并行訪問陣列，并對布林值執行測驗和設定操作。如果已設定，則將數字分配給重復并增加計數。
此解決方案可能并不總是比建議的順序替代方案執行得更好。如果所有數字都是重復的，當然不會。盡管如此，它在理論上具有恒定的復雜性。或者可能是重復數量的線性復雜性。我不太確定。但是，它在使用多個內核時應該表現良好，尤其是在測驗和設定和增量操作是無鎖的情況下。
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/485810.html
上一篇：我正在研究演算法，它只在1種情況下給出錯誤（運行時錯誤）
下一篇：查找單鏈表中的最后一個K