數組中的重複項 - 可能在o（n）中解決？

Question

我已經創建，其檢測在陣列中重複一個代碼，我認爲沒有一種算法，比該速度快：

import java.util.HashSet; 
import java.util.Set; 

    public class Dupe 
    { 
     public static void main (String[] args) 
     { 
      int[] myArray = {1, 2, 2, 3, 1, 4, 5, 6, 7, 4}; 
      Set<Integer> set = new HashSet<>(); 

      for (int a : myArray) 
      { 
       if (!set.add(a)) 
       { 
        System.out.println(a); 
       } 
      } 
     } 
    } 

它在O（N）。在o（n）中也可以解決這個問題嗎？

Answer 1

當然，至少有一次你不得不經過陣列，而你正在做它。因此，爲了檢查是否有重複項，您可以在O(n) ° F(n)（可以是+或*）中執行此操作，因此您唯一需要做的事情是確保您不會提高速度，因此您需要將​​。檢查Set中是否有內容O(1)，所以你只剩下O(n)，就是這樣。