這段代碼中的錯誤是什麼？

基於一個this邏輯給出了對不同（類似）問題的SO的答案，爲了在O（N）時間複雜度中刪除數組中的重複數字，我在C中實現了該邏輯，如下所示。但我的代碼的結果不會返回唯一的數字。我嘗試過調試，但無法獲得它的邏輯來解決這個問題。這段代碼中的錯誤是什麼？

int remove_repeat(int *a, int n) 
{ 
    int i, k; 

    k = 0; 
    for (i = 1; i < n; i++) 
    { 
     if (a[k] != a[i]) 
     { 
      a[k+1] = a[i]; 
      k++;    
     } 
    } 
    return (k+1); 
} 

main() 
{ 
    int a[] = {1, 4, 1, 2, 3, 3, 3, 1, 5}; 
    int n; 
    int i; 

    n = remove_repeat(a, 9); 

    for (i = 0; i < n; i++) 
      printf("a[%d] = %d\n", i, a[i]); 


}

1]在上面的代碼中刪除重複項有什麼不正確。

2]此問題的任何其他O（N）或O（NlogN）解決方案。它的邏輯？

來源

2011-07-17 goldenmean

當你嘗試調試時你學到了什麼？ –

你的意圖不清楚。我很清楚它不起作用，請用你自己的話來描述你想要編碼的東西。 – Drakosha

@Cody - 這個邏輯試圖建立一個從0到j唯一數字的子數組。 – goldenmean

您的代碼只檢查數組中的項是否與其前一個相同。

如果你的數組開始排序，那將起作用，因爲特定數字的所有實例都是連續的。

如果陣列是沒有排序下手，這是行不通的，因爲一個特定數量的情況下，可能不會是連續的，所以你必須通過所有前面的數字來看看，以確定一個人是否已經看到然而。

要做到在澳工作（N日誌N）的時候，你可以對數組進行排序，然後使用您已有的邏輯從數組排序刪除重複。顯然，這隻有在你重新排列數字的時候纔有用。

如果你想保留原來的訂單，你可以使用類似哈希表或位設置來跟蹤一個數字是否已經被查看或沒有，只有當每個數字複製到輸出/如果沒有尚未見過。要做到這一點，我們改變當前的：

if (a[k] != a[i]) 
    a[k+1] = a[i];

喜歡的東西：

if (!hash_find(hash_table, a[i])) { 
    hash_insert(hash_table, a[i]); 
    a[k+1] = a[i]; 
}

如果你的號碼都屬於相當狹窄的範圍內，或者預期的值是密集的（即最值目前）你可能想要使用一個位集而不是一個哈希表。這只是一個位數組，設置爲零或一個來指示是否已經看到特定的數字。

在另一方面，如果你更關心的是上界的複雜性比一般情況下，你可以使用一個平衡基於樹的集合，而不是一個哈希表。這通常會使用更多的內存並且運行速度更慢，但其預期的複雜度和最壞的情況複雜度基本相同（O（N log N））。在最壞的情況下，典型的哈希表從簡單的複雜性退化爲線性複雜性，這會將整體複雜度從O（N）變爲O（N ）。

來源

2011-07-17 15:48:57

您將需要兩個循環，一個通過源代碼，一個檢查目標數組中的每個項目。

你是不是會得到O（N）。

[編輯] 您鏈接到文章建議一個排序輸出陣列，這意味着在輸出陣列中的重複項搜索可以是二進制搜索...這是O（logn）時間。

來源

2011-07-17 15:11:54

我以爲文章說：「從元素進行量[1 ]到a [N]。在每個階段i，a [i]左邊的所有元素包含一個元素a [0]到[j]的排序堆。對於i的每次迭代，意味着在[]中，i中左邊的元素是通過這個邏輯獲得的排序元素？我錯過了什麼嗎？ – goldenmean

我編輯了我原來的帖子。 –

堆排序在O（n日誌n）時間。
迭代O（n）時間替換具有標記值的重複元素（例如INT_MAX）。
堆再次在O（n log n）中排序以提取重複元素。

仍然以O（n log n）爲界。

來源

2011-07-17 15:13:19

您的代碼似乎需要輸入排序。如果您使用的是未分類輸入，則代碼不會刪除所有重複項（僅限於相鄰項）。

來源

2011-07-17 15:14:26 Iridium

你的邏輯錯了，所以代碼也是錯的。在編寫代碼之前，請自行編寫邏輯代碼。我建議O（NlnN）方式修改heapsort。隨着heapsort，我們從[i]加入到[n]，找到最小值並將其替換爲[i]，對不對？所以現在是修改，如果最小值與[i-1]相同，然後交換最小值和a [n]，則將您的數組項目的編號減少1. 它應該以O（NlnN）方式執行。

來源

2011-07-17 15:21:17

如果整數的數量是預先知道的並且小於您擁有的內存量，那麼您可以得到O（N）解決方案。進行一次確定使用輔助存儲器的唯一整數，然後再輸出唯一值。

下面的代碼是用Java編寫的，但希望你能明白。

int[] removeRepeats(int[] a) { 
    // Assume these are the integers between 0 and 1000 
    Boolean[] v = new Boolean[1000]; // A lazy way of getting a tri-state var (false, true, null) 

    for (int i=0;i<a.length;++i) { 
     v[a[i]] = Boolean.TRUE; 
    } 

    // v[i] = null => number not seen 
    // v[i] = true => number seen 

    int[] out = new int[a.length]; 
    int ptr = 0; 
    for (int i=0;i<a.length;++i) { 
     if (v[a[i]] != null && v[a[i]].equals(Boolean.TRUE)) { 
      out[ptr++] = a[i]; 
      v[a[i]] = Boolean.FALSE;   
     } 
    } 

    // Out now doesn't contain duplicates, order is preserved and ptr represents how 
    // many elements are set. 
    return out; 
}

來源

2011-07-17 15:22:51

請注意，你有O（整數的數量）:) – Drakosha

@Jeff - 如果我有-ve數字，這不起作用，不是這樣。查找數字是否被看到的第一步可能會失敗？有什麼想法嗎？ – goldenmean

@Drakosha所有的循環都在輸入數組上，所以我認爲O（N）？或者我誤解了？ @GoldenMean，如果你有一個受約束的宇宙（例如數字在-50到50之間，那麼你可以簡單地轉換值），這與使用散列表來存儲數字的計數基本相同，只是使用完美的散列傳統陣列的+桶或樹的實現 –

您的代碼只能在特定的情況下工作。顯然，你正在檢查相鄰的值，但重複的值可能出現在數組中的任何位置。因此，這是完全錯誤的。

來源

2011-07-17 17:20:30 schrodinger

這段代碼中的錯誤是什麼？

回答

相關問題