Duplikate in Array - möglich in o (n) zu lösen?

Question

ich einen Code erstellt haben, die Duplikate in einem Array erkennt, ich glaube es nicht einen Algorithmus, der schneller ist als das ist:

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); 
       } 
      } 
     } 
    } 

Es ist in O (n). Wäre es auch möglich, dies in o (n) zu lösen?

Answer 1

Natürlich gibt es nicht, da Sie Array mindestens einmal durchlaufen müssen, und Sie tun es. Also, um zu überprüfen, ob Sie Duplikate haben, werden Sie es in O(n) ° F(n) (kann + oder *) tun., So dass Sie nur übrig bleiben, ist sicherzustellen, dass Sie diese Geschwindigkeit nicht erhöhen, so dass Sie F(n) minimieren müssen . Überprüfen, ob etwas in Set ist O(1), so dass Sie mit O(n) verlassen werden, und das ist es.