numer, który pojawia się więcej niż n/3 razy w tablicy

Question

przeczytałem ten problem Find the most common entry in an array

i odpowiedź od Jon Skeet jest po prostu niewiarygodny .. :)

Teraz staram się rozwiązać ten problem znajduje element, który występuje więcej niż n/3 razy w tablicy ..

Jestem prawie pewien, że nie możemy zastosować tej samej metody, ponieważ mogą istnieć 2 takie elementy, które wystąpią więcej niż n/3 razy i to daje fałszywy alarm w obliczeniach ... czy jest jakiś sposób, żeby poprawić odpowiedź Jona Skeeta na pracę w tym ...?

Czy istnieje jakieś rozwiązanie, które będzie działać w czasie liniowym?

Answer 1

Jan Dvorak's answer jest prawdopodobnie najlepiej:

• start z dwóch pustych gniazd kandydujących oraz dwóch liczników ustawiony na 0.
• dla każdej pozycji:
  • jeśli jest ona równa albo kandydata , inkrementuj odpowiedni licznik:
  • w przeciwnym razie, jeśli jest puste miejsce (tj. slot z liczbą 0), umieść go w tym gnieździe i ustawić liczyć do 1
  • innego zmniejszyć oba liczniki przez 1

Na koniec wykonać drugie podaniem w tablicy, aby sprawdzić, czy kandydaci naprawdę mają wymaganą liczbę. Jest to niedozwolone przez pytanie, które łączysz, ale nie widzę sposobu, aby tego uniknąć w przypadku tej zmodyfikowanej wersji. Jeśli istnieje wartość, która występuje więcej niż n/3 razy, to znajdzie się w gnieździe, ale nie wiesz, który to jest.

Jeśli to zmodyfikowana wersja pytanie zagwarantować, że nie było dwa wartości o więcej niż n/3 elementów (w ogóle, k-1 wartości z ponad n/k) wtedy nie potrzebujesz drugiego przebiegu. Ale kiedy oryginalne pytanie ma k=2 i 1 gwarantowaną większość, nie ma sposobu, aby dowiedzieć się, czy "powinniśmy" uogólnić to jako gwarantujące 1 taki element lub gwarantując k-1. Im większa gwarancja, tym łatwiejszy problem.

Answer 2

Możesz użyć numeru Selection algorithm, aby znaleźć numer w miejscu n/3 i 2n/3.

n1=Selection(array[],n/3); 
n2=Selection(array[],n2/3); 
coun1=0; 
coun2=0; 

for(i=0;i<n;i++) 
{ 
    if(array[i]==n1) 
     count1++; 
    if(array[i]==n2) 
     count2++; 
} 
if(count1>n) 
    print(n1); 
else if(count2>n) 
    print(n2); 
else 
    print("no found!"); 

Answer 3

Korzystanie Boyer-Moore większości głosów algorytm, otrzymujemy:

vector<int> majorityElement(vector<int>& nums) { 
    int cnt1=0, cnt2=0; 
    int a,b; 
    for(int n: nums){ 
     if (cnt1 == 0 || n == a){ 
      cnt1++; 
      a = n; 
     } 
     else if (cnt2 == 0 || n==b){ 
      cnt2++; 
      b = n; 
     } 
     else{ 
      cnt1--; 
      cnt2--; 
     } 
    } 
    cnt1=cnt2=0; 
    for(int n: nums){ 
     if (n==a) cnt1++; 
     else if (n==b) cnt2++; 
    } 
    vector<int> result; 
    if (cnt1 > nums.size()/3) result.push_back(a); 
    if (cnt2 > nums.size()/3) result.push_back(b); 
    return result; 
} 

Answer 4

Na linii numer pięć, oświadczenie if powinien mieć jeszcze jeden czek:

if(n!=b && (cnt1 == 0 || n == a))