Znajdź element, który pojawia się raz.

Question

Znajdź element, który pojawia się raz.

Podana jest tablica, w której każdy element występuje trzy razy, z wyjątkiem jednego elementu, który występuje tylko raz. Znajdź element, który występuje raz.

Oczekiwana złożoność czasu to O (n) i O (1) dodatkowa przestrzeń.

Przykłady:

Wejście: ARR [] = {12, 1, 12, 3, 12, 1, 1, 2, 3, 3}

wyjściowy: 2

Answer 1

Jeśli wyjścia (1) nie istniało ograniczenie przestrzeni, mogłeś poszukać hashmapy z wartościami będącymi liczbą wystąpień.

int getUniqueElement(int[] arr) 
{ 
    int ones = 0 ; //At any point of time, this variable holds XOR of all the elements which have appeared "only" once. 
    int twos = 0 ; //At any point of time, this variable holds XOR of all the elements which have appeared "only" twice. 
    int not_threes ; 

    for(int x : arr) 
    { 
     twos |= ones & x ; //add it to twos if it exists in ones 
     ones ^= x ; //if it exists in ones, remove it, otherwise, add it 

     // Next 3 lines of code just converts the common 1's between "ones" and "twos" to zero. 

     not_threes = ~(ones & twos) ;//if x is in ones and twos, dont add it to Threes. 
     ones &= not_threes ;//remove x from ones 
     twos &= not_threes ;//remove x from twos 
    } 
    return ones; 
} 

Zasadniczo, to korzysta z faktu, że x^x = 0 i 0^x=x. Tak więc wszystkie sparowane elementy otrzymują XOR i znikają pozostawiając samotny element.

W skrócie:

Jeżeli bit jest już w nich, dodaj go do Dwójki.

XOR doda ten bit do tych bitów, jeśli ich tam nie ma lub usunie ten bit z tych, jeśli już tam jest.

Jeśli bit jest w dwóch lub w jednym, usuń go z jednego i dwóch.

Po zakończeniu te zawierają bity, które pojawiły się tylko 3 * n + 1 razy, które są bitami dla elementu, który pojawił się tylko raz.

Answer 2

Zgodnie z opisem here, medianę elementów tablicy można znaleźć w najgorszym przypadku czasu O (n) i O (1) dodatkowego miejsca. Tak więc możemy rozwiązać problem metodą dziel i rządź:

Znajdź medianę w czasie O (n) i policz liczbę elementów, które są mniejsze lub równe medianie w O (n). Jeśli ta liczba to 3k + 1, oznacza to, że odpowiedź jest mniejsza lub równa medianie, więc pomiń elementy, które są większe niż mediana w O (n). Inaczej, pomiń te, które są mniejsze lub równe medianie. Następnie rekursywnie znajdź odpowiedź w pozostałych elementach w T (n/2). Uwaga: liczba pozostałych elementów to n/2, ponieważ pominęliśmy połowę elementów.

Więc T (n) = T (n/2) + O (n) = O (n) i potrzebujemy O (1) dodatkowej przestrzeni.

Answer 3

Proponuję rozwiązanie podobne do rozwiązania proponowanego przez mhsekhavata. Zamiast określać medianę, proponuję użyć algorytmu podziału holenderskiego problemu narodowej flagi http://en.wikipedia.org/wiki/Dutch_national_flag_problem (tak, jestem holenderski i wykształcony w stylu Dijkstry).

Wynikiem zastosowania algorytmu jest tablica podzielona na część czerwoną, białą i niebieską. Białą część można uznać za oś obrotu. Zwróć uwagę, że biała część składa się ze wszystkich elementów równych czopowi, więc biała część będzie zawierała 1 lub 3 elementy. Część czerwona składa się z elementów mniejszych niż oś przestawna, a część niebieska składa się z elementów większych niż oś przestawna. (Zwróć uwagę, że czerwone i niebieskie części nie są posortowane!)

Następnie policz liczbę elementów części czerwonej, białej i niebieskiej. Jeśli jakaś część składa się z 1 elementu, to jest to liczba, której szukasz.W przeciwnym razie część czerwona lub niebieska składa się z elementów 3k + 1, dla danej liczby k. Powtórz algorytm na części składającej się z 3k + 1 elementów. Ostatecznie jedna z części będzie miała rozmiar 1.

Algorytm działa w O (n) i wymaga zmiennych O (1).

Answer 4

rozwiązanie JavaScript:

function findElement(arr) { 
    var ones = 0; 
    var twos = 0; 
    for (var i = 0; i < arr.length; i++) { 
    ones = (ones^arr[i]) & ~twos; 
    twos = (twos^arr[i]) & ~ones; 
    } 
    return ones; 
} 

Answer 5

Choć pytanie jest już odpowiedź, znalazłem następujące bardziej intuicyjne, a więc dodanie go jako odpowiedź. Pochodzi z here

int singleNumber(vector<int>& nums) { 
    /*Bits in 'ones' are set to 1, when that particular bit 
     occurs for the first time. Bits in 'twos' are set to 1, 
     when that particular bit occurs for the second time. If a 
     bit is occurring for more than 2 times, we throw it away 
     and start counting again.*/ 
    int ones = 0; 
    int twos = 0; 
    for (auto elem : nums) { 
     int onesOld = ones; 
     /* (ones^elem): consider the ith bit in 'ones' be 0 (i.e. ith 
      bit has not occurred till now or has occurred 2 times) and in 
      'elem' be 1. So, for the ith bit (ones^elem) gives 1. Now, 
      ith bit could have occurred even number of times as well (i.e. 
      ith bit in twos is set to 1). If that was the case, we 
      would like to ignore such bit. This last part is taken care 
      of by '&' with '~twos' 
      */ 
     ones = (ones^elem) & ~twos; 
     /* (onesOld & elem) gives the bits which have occurred ones 
      and also occur in this particular element. (twos & ~elem) 
      gives the bits that have occurred twice and do not occur 
      in this element. Both these cases take care of the bits 
      that have occurred 2 times (although a bit might be set 
      more than 2 times, like 5,7... but we take only modulo 3 
      count). 
     */ 
     twos = (onesOld & elem) | (twos & ~elem); 
    } 
    return ones; 
}