Linearer Scan zum Vergleichen zweier Arrays in Java

Question

Ich versuche gerade, einen Algorithmus zu schreiben, der mit Hilfe von Java zwei Arrays auf Gleichheit in O (N) -Zeit scannen kann. Die Idee ist, dass die Arrays unabhängig von der Reihenfolge genau gleich sein sollten, damit die Methode "true" zurückgibt. Was mir empfohlen wurde, war die Verwendung von linearem Scan, aber eine Schleife zum Scannen und Vergleichen von zwei Arrays. Das ist, was ich habe:

public boolean equals(ArraySet<T> s) { 
    T[] sArray = s.getArray(); 
    boolean isEqual = true; 
    if (!(s.size() == size())) { 
    return false; 
    } 
    int i = 0; 
    int p = 0; 
    while ((i < elements.length) && (p < sArray.length)) { 
    if (elements[i].compareTo(sArray[p]) != 0) { 
     isEqual = false; 
     p++; 
     continue; 
    } 
    i++; 
    p = 0; 
    isEqual = true; 
    } 
    return isEqual; 

Ich bin zuversichtlich, dass dieser Algorithmus korrekt die Gleichheit zurückkehren wird, aber ich bin nicht so sicher, dass es so in O (N) Zeitkomplexität zu tun. Kann ich etwas optimieren, um sicherzustellen, dass diese Methode mit der richtigen Effizienz funktioniert? ArraySet ist eine Set-Implementierung, die ein Array-Feld enthält, das von getArray() zurückgegeben wird. Es kann angenommen werden, dass dieses Array und das lokale Array bereits in aufsteigender natürlicher Reihenfolge sind, jedoch kann nicht davon ausgegangen werden, dass das Parameterarray und das lokale Array die gleichen Elemente aufweisen.

Answer 1

Zunächst einmal ist das, was Sie in Ihrer while-Schleife tun, nicht korrekt. Szenario 1: Selbst wenn wir annehmen, dass beide Arrays sortiert sind, erhöhen Sie in Ihrer while-Schleife nur p und nicht i. Das heißt, wenn Sie zwei Arrays haben: element = {1,2,3} sArray = {1,2,3}; Sie vergleichen nur Element [0] mit Rest von sArray.

Szenario 2: Nehmen wir an, beide Arrays sind gleich lang, aber nicht in sortierter Reihenfolge. Element = {1,2,3} sArray = {2,1,3}; Auch hier vergleicht dein Code wieder element [0] mit dem Rest des sArray.

Ein besserer Ansatz besteht darin, ein HashSet zu verwenden und Ihr Elementarray mit dem Hashset zu vergleichen. Hier ist ein einfaches Beispiel zu Arrays vergleichen: [wir vorausgesetzt, es gibt keine Duplikate in den beiden Arrays, sonst diese Lösung nicht funktionieren]

Set<Integer> uniqueList = new HashSet<Integer>(); 
     int[] elements={1,2,3}; 
     int[] sArray = {3,2,1}; 
     boolean isArrayElementsEqual = false; 

     for(int i=0;i<sArray.length;i++){ 
      uniqueList.add(sArray[i]);// add one of the arrays complete elements into a set 
     } 

     for(int i=0;i<elements.length;i++){ 
      if(uniqueList.contains(elements[i])){//compare another array elements with the set, if its exists them remove it from set..such that by the end of this if both arrays have equal contents, set should be empty 
       uniqueList.remove(elements[i]); 

      } 
     } 

     if(uniqueList.isEmpty()){//if this list is empty it means both arrays have same contents 
      isArrayElementsEqual = true; 
      return isArrayElementsEqual; 
     } 

     return isArrayElementsEqual; 

PS: Sie können es ändern, basierend auf Ihrer Anforderung