陣列 - 杜佩掃描儀和算法

1）創建一個算法，它會檢測是否有重複（=相同的數字），陣列中的（更好的運行時間，我得到的點數越多）。

2.）分析算法的運行時間。

這裏是我的第一個任務的代碼（我有這樣的算法工作更快/在所有工作數組排序爲此，我使用import而不是編碼它自己。）：

import java.util.Arrays; 

public class Dupescanner 
{ 
    public static void main(String[] args) 
    { 
     int[] A = {1, 2, 3, 4, 5, 1, 2, 8, 8}; 
     Arrays.sort(A); 
     System.out.println("Following numbers are duplicates:"); 
     for (int n = 1; n < A.length; n++) 
     { 
      if (A[n] == A[n - 1]) 
      { 
       System.out.println(A[n]); 
      } 
     } 
    } 
}

輸出：

Following numbers are duplicates: 
1 
2 
8

那算法很好嗎？我想不出比這個更快的東西。或者，也許我誤解了這項任務，如果你只是說：是真的 - 有/是重複的。假 - 不...

對於運行時分析，我不知道，但我給它一個嘗試，以及：

int[] A = {1, 2, 3, 4, 5, 1, 2, 8, 8};

加1

for循環成本n和若成本也是。結果將是n^2 + 1.另外我不確定數組排序是否重要，我排除它。

來源

2016-04-26 tenepolis

如果你有java 8，你可以使用並行流 – mariusz2108

@ mariusz2108儘管這與這個問題無關。 – Kayaman

@tenepolis數組排序不會計數。你不能僅僅因爲你沒有爲它寫代碼就排除它。 – Kayaman

你的算法是O(nlogn)，這裏的瓶頸就是排序。

您的循環以線性時間運行。

這實際上是element distinctness problem。

只有在允許散列和額外空間的情況下，通過填充散列表（HashSet），以及在迭代時將所有元素插入到散列表中，並且如果找到僞指令，則可以更有效地解決它（根據漸近複雜度）同時迭代 - 打印它。

int[] array = {1, 2, 3, 4, 5, 1, 2, 8, 8}; 
Set<Integer> set = new HashSet<>(); 
System.out.println("Following numbers are duplicates:"); 
for (int e : array) { 
    if (!set.add(e)) System.out.println("" + e); 
}

This thread討論了這個問題下限。

來源

2016-04-26 18:48:45 amit

陣列 - 杜佩掃描儀和算法

回答

相關問題