在帶有邊界的整數數組中找到重複項

Question

下面是我寫的問題描述和算法。有什麼需要改進這個算法嗎？

給定一個未知大小的整數數組，只包含0到30之間的數字，編寫一個函數返回一個包含所有重複項的整數數組。

int[] findDupes(int[] array) { 
    int[] found = new int[30]; 
    int[] dupes = new int[30]; 
    int dupesCount = 0; 
    for (int i = 0; i < array.length; i++) { 
     if (found[array[i]] <= 1) { 
      found[array[i]]++;    
     }else{ 
      continue; 
     } 
     if(found[array[i]] > 1){ 
      dupes[dupesCount++] = array[i]; 
      if (dupesCount == 30) 
       break; 
     } 
    } 
    if (dupesCount == 0) 
     return new int[0]; 
    return dupes; 
} 

上午假定運行此算法最好的情況下將n或30孰低 以及運行該算法最壞的情況是n，因爲我要掃描整個陣列，以查找重複。任何意見？

Answer 1

這裏是嵌入了評論的修改版本。

int[] found = new int[3]; 
    int[] dupes = new int[3]; 
    int dupesCount = 0; 
    for (int i = 0; i < array.length; i++) { 
     if (found[array[i]] <= 1) { 
      found[array[i]]++;    
     } 
     if(found[array[i]] > 1){ //duplicate found 
      dupes[dupesCount++] = array[i]; 

      // if 30 duplicate are found don't scan the array any more 
      // since the distinct numbers are only 30 
      if (dupesCount == 30) 
       break; 
     } 
    } 
    if (dupesCount == 0) 
     return null; 
    return dupes; 

Answer 2

你有正確的想法，但問自己，這是什麼做的塊，正是

if(found[array[i]] > 1){ 
     dupes[dupesCount++] = array[i]; 
     if (dupesCount == 30) 
      break; 
    } 

當它火？

通過與一對夫婦的樣本包括1000次的0

你到底是什麼返回數組的代碼走？爲什麼你需要特殊情況下0.

此外，最好的情況下運行時間將會大於30.什麼是最低輸入，使它在達到結束之前停止？

Answer 3

奇怪的事情：

if (found[array[i]] <= 1)    
    }else{ 
     continue;//happens if found[array[i]] > 1 
    } 
    if(found[array[i]] > 1){//usually don't get here, because of continue 

是在不斷的修復，只添加一個數字一次？雖然它起作用，但代碼具有誤導性。

如果只有一個重複項，您是否必須返回一個30長度的數組？

我建議通過分割任務讓你的代碼變得更慢更好。

Answer 4

需要更精確的問題定義。是否只有1或2次出現整數？可以有0或3次發生？

如果只有1或2次出現的整數，整數範圍從1到30;我會有一個BitSet，並翻轉位，因爲我找到一個整數。當我完成讀取原始數組時，所有0的位將表示包含重複的整數。