Jaki jest optymalny sposób obliczania, która liczba całkowita na liście brakuje?

Question

Niedawno byłem w wywiadzie, w którym zadawali mi pytania techniczne. Jednym z nich był sposób obliczania, którego numeru na liście o długości n-1 brakowało. Lista zawierała każdą liczbę od 1 do n, z wyjątkiem i gdzie 1 < = i < = n. Numery nie były w porządku. Moim rozwiązaniem było dodanie ich wszystkich, a następnie odjęcie ich od obliczeń liczb od 1 do n, przez dodanie od 1 do n i pomnożenie przez n/2 lub (n-1)/2, stosownie do potrzeb. Ale miałem poczucie, że jest lepszy sposób na zrobienie tego. Jakie jest optymalne rozwiązanie?

Answer 1

Twoja odpowiedź jest wystarczająco dobra, moim zdaniem.

Ale niektórzy ludzie - być może twój ankieter jest jednym z nich - martwią się przepełnieniem i takimi. W takim przypadku użyj XOR zamiast dodawania.

Aby uzyskać XOR z liczb całkowitych od 0 do n, po prostu XOR razem tablica indeksuje się w pętli. Biorąc pod uwagę XOR liczb całkowitych od 0 do n oraz XOR elementów tablicy, po prostu XOR dwa z nich razem, aby uzyskać brakujący element.

P.S. Suma liczb całkowitych od 1 do n jest zawsze (n + 1) * n/2

Answer 2

podczas iteracji przez tablicę w celu obliczenia sumy, można sprawdzić, czy numer jest powtarzany.

Answer 3

Twoja metoda jest absolutnie w porządku. Jest optymalny zarówno pod względem przestrzeni, jak i czasu. Overflow może być jedynym problemem z tym.

Inną możliwą metodą może być użycie hashSet. Utwórz początkowy hashSet mający wartości 1-> N. Teraz dla każdego numeru, który napotkasz na liście - usuń tę wartość z hashSet. Na końcu wartość, która pozostaje w haszymencie, jest brakującą wartością.

Ta metoda jest O (N) w złożoności czasu i przestrzeni. Twoja metoda (przekroczenie zakazu) to O (N) w czasie i złożoność O (1). Dodatkowym czynnikiem "n" dla miejsca jest koszt eliminacji przepełnienia.

Answer 4

Twoje rozwiązanie jest dość dużo optymalna z jedną zmianą, jak @Nemo wskazuje na sumę liczb od 1 do n jest zawsze (n+1) * n/2

Warto również podkreślić, że podejście jest wielowątkowym zdolny (i moc nadaje się do bardzo dużych wartości N), dzieli tablicę na części, a następnie pobiera sumę każdej części tablicy w wątku, a następnie dodaje te sumy części. Zależy to od tego, w jaki sposób narzut gwintowania jest porównywany z dodawaniem liczb w tablicy.

Jeśli martwisz się o przepełnienie, a Twoje wartości są zawsze Int32 (jak większość wartości .Length są w tym tablice), a następnie po prostu zapisać sumę jako Int64, suma wszystkich dodatnich liczb całkowitych wartości (((long)int.MaxValue) +1L) * (int.MaxValue/2) = 2305843007066210304 który jest nadal w stanie dopasować w obrębie int64 z .MaxValue = 9223372036854775807.

Inną odpowiedzią, o której wspominali inni, jest XOR dla każdego przedmiotu i prowadzenie XOR, ale wtedy trzeba opracować formułę, aby uzyskać oczekiwany całkowity XOR w czasie O(1).

Najprawdopodobniej ankieter jest sprawdzanie, czy zdajesz sobie sprawę, że AN O(N) rozwiązanie z O(1) pamięci (które odpowiedź brzmi), zamiast sortowania tablicy i jest znacznie wolniejszy o bardzo dużych wartościach N.

Aby jeszcze bardziej ulepszyć twoje rozwiązanie w kodzie, użyłbym wskaźnika do uzyskania dostępu do tablicy, a nie do wartości indeksu (która, jeśli twój kod jest C#, będzie sensownym ulepszeniem).