Getting a Different Number

[esthicodes]

Getting a Different Number

    n = arr.length

    # since we’re not allowed to modify arr, we create a copy of it
    arrSorted = new Array(arr)

    # sort the duplicate array in an ascending order
    arrSorted.sort()

    for i from 0 to n - 1:
        if (arrSorted[i] != i):
            return i  # i isn’t in arr, hence we can return it

    # we got here since every number from 0 to n-1 is in arr.
    # By definition then, n isn’t in arr. Otherwise, the size of arr
    # would have been n+1 and not n.
    return n```


```function getDifferentNumber(arr):
    n = arr.length

    set = new Set() # the Set interface is language dependent
    for i from 0 to n-1:
        set.insert([arr[i]]) # build the set

    for i from 0 to n - 1:
        if (set.find(i) == false):
            return i

    # we got here since every number from 0 to n-1 is in arr.
    # By definition then, n isn’t in arr. Otherwise, the size of arr
    # would have been n+1 and not n.
    return n```


```function getDifferentNumber(arr):
    n = arr.length
    temp = 0

    # put each number in its corresponding index, kicking out
    # the original number, until the target index is out of range.
    for i from 0 to n-1:
        temp = arr[i]
        while (temp < n AND arr[temp] != temp):
            swap(temp, arr[temp])

    for i from 0 to n - 1:
        if (arr[i] != i):
            return i  # i isn’t in arr, hence we can return it

    # we got here since every number from 0 to n-1 is in arr.
    # By definition then, n isn’t in arr. Otherwise, the size of arr
    # would have been n+1 and not n.
    return n```

[esthicodes]

Eine supernaive Lösung besteht darin, zufällig Zahlen von 0 bis MAX_INT auszuwählen und zu prüfen, ob sie in arr sind. Dies ist jedoch kein guter Ansatz. Erstens hat das Worst-Case-Szenario nicht einmal eine Obergrenze. Wir könnten sehr unglücklich sein und Zahlen zurückziehen, die sich im Array befinden. Wenn die Größe von arr sehr groß ist, müssen wir außerdem viele Male nach den Zufallszahlen in diesem Array suchen. Eine andere einfache Lösung besteht darin, das Minimum/Maximum aufzuzeichnen, während alle Zahlen in arr durchlaufen werden, und dann Zahlen zu erzeugen, die kleiner/größer als alle Zahlen in arr sind. Dies funktioniert jedoch nicht, wenn die Mindestzahl 0 und die Höchstzahl MAX_INT ist. Eine andere Iterationstaktik ist die Rückgabe der Summe aller Zahlen, aber sie funktioniert zum Beispiel nicht für das Array [0, 3]. Außerdem wäre die Rückgabe der Multiplikation aller Zahlen in arr nicht korrekt, wenn 0 eine der Zahlen in arr ist.

[esthicodes]

    n = arr.length

    # since we’re not allowed to modify arr, we create a copy of it
    arrSorted = new Array(arr)

    # sort the duplicate array in an ascending order
    arrSorted.sort()

    for i from 0 to n - 1:
        if (arrSorted[i] != i):
            return i  # i isn’t in arr, hence we can return it

    # we got here since every number from 0 to n-1 is in arr.
    # By definition then, n isn’t in arr. Otherwise, the size of arr
    # would have been n+1 and not n.
    return n```