Beschleunigung Swift CodeFight Herausforderung

Question

Per Codefighters:

Hinweis: Um eine Lösung mit O (n) Zeit Komplexität und O (1) zusätzlichem Raum Komplexität schreiben, da dies ist, was Sie bei einem echten Interview dazu aufgefordert werden würden .

Geben Sie für ein Array a, das nur Zahlen im Bereich von 1 bis a.length enthält, die erste doppelte Zahl an, für die das zweite Vorkommen den minimalen Index hat. Mit anderen Worten, wenn es mehr als 1 doppelte Nummern gibt, geben Sie die Zahl zurück, für die das zweite Vorkommen einen kleineren Index hat als das zweite Vorkommen der anderen Nummer. Wenn keine solchen Elemente vorhanden sind, geben Sie -1 zurück.

Beispiel

Für a = [2, 3, 3, 1, 5, 2], sollte die Ausgabe firstDuplicate sein (a) = 3.

sind 2 Dubletten: Zahlen 2 und 3 Das zweite Vorkommen von 3 hat einen kleineren Index als das zweite Vorkommen von 2, also lautet die Antwort 3.

Für a = [2, 4, 3, 5, 1] ​​sollte der Ausgang firstDuplicate sein (a) = -1.

Also hier ist, was ich gefunden habe. Es funktioniert, aber scheitert am letzten Test, weil es über 4000ms lief. Ich bleibe bei dem, was ich noch tun kann. Irgendwelche Ideen, um die Geschwindigkeit zu verbessern?

func firstDuplicate(a : [Int]) -> Int { 
var duplicateIndexArray = [Int]() 
for firstIndex in 0..<a.count { 

    for secondIndex in 0..<a.count { 

     if a[firstIndex] == a[secondIndex] && firstIndex != secondIndex { 
      print(firstIndex, secondIndex) 
      if !(duplicateIndexArray.contains(firstIndex)){ 
       duplicateIndexArray.append(secondIndex) 
       break 
      } 
     } 
    } 
} 

// Check for duplicacy 
if duplicateIndexArray.count > 0 { 
    print(duplicateIndexArray) 
    return a[duplicateIndexArray.min()!] 
} 
return -1 

}

Answer 1

Der O (n) Zeitteil ist einfach, aber die O (1) zusätzlicher Raum ist ein wenig kompliziert. Normalerweise kann ein Hash-Satz (oder ein Bit-Array in Ihrem Fall) verwendet werden, um zu überprüfen, ob eine Zahl mehr als einmal aufgetreten ist, aber das erfordert O (n) zusätzlichen Speicherplatz. Für O (1) zusätzlichen Raum können wir das Quell-Array selbst als ein Bit-Array verwenden, indem wir einige der Zahlen darin negativ machen.

Zum Beispiel, wenn die erste Zahl im Array 3 ist, dann machen wir die Zahl an der Position 3-1 negativ. Wenn eine der anderen Zahlen im Array ebenfalls 3 ist, können wir prüfen, ob die Zahl an Position 3-1 negativ ist.

Ich habe keine Erfahrung mit Swift, also werde ich versuchen, eine Funktion in pseudocode zu schreiben:

function firstDuplicate(a) 
    result = -1 

    for i = 0 to a.count - 1 
     if a[abs(a[i])-1] < 0 then 
      result = a[i] 
      exit for loop 
     else 
      a[abs(a[i])-1] = -a[abs(a[i])-1] 

    // optional restore the negative numbers back to positive 
    for i = 0 to a.count - 1 
     if a[i] < 0 then 
      a[i] = -a[i] 

    return result 

Answer 2

Ersetzen Sie diese Zeile

for secondIndex in 0..<a.count 

mit

for secondIndex in firstIndex..<a.count 

Es ist keine Doppelprüfung erforderlich

So ist Ihr endgültiger Code

func firstDuplicate(a : [Int]) -> Int { 
    var duplicateIndexArray = [Int]() 
    for firstIndex in 0..<a.count { 

     for secondIndex in firstIndex..<a.count { 

      if a[firstIndex] == a[secondIndex] && firstIndex != secondIndex { 
       print(firstIndex, secondIndex) 
       if !(duplicateIndexArray.contains(firstIndex)) 
       { 
        duplicateIndexArray.append(secondIndex) 
        break 
       } 
      } 
     } 
    } 

    // Check for duplicacy 
    if duplicateIndexArray.count > 0 
    { 
     print(duplicateIndexArray) 
     return a[duplicateIndexArray.min()!] 
    } 
    return -1 
}