Il Tempo Lineare Algoritmo Di Voto. Non la capisco

Mentre stavo leggendo questo (Trovare la voce più comune in un array), il Boyer Moore e di Tempo Lineare Algoritmo di Voto è stato suggerito.

Se si segue il link al sito, c’è una spiegazione passo passo di come funziona l’algoritmo. Per la sequenza data, AAACCBBCCCBCC si presenta la giusta soluzione.

Quando si sposta il puntatore in avanti rispetto
un elemento e:

  • Se il contatore è a 0, abbiamo impostato l’attuale candidato a e e abbiamo impostato il
    contatore a 1.
  • Se il contatore non è 0, è possibile incrementare o decrementare il contatore
    secondo se i è la corrente
    candidato.

Quando abbiamo finito, l’attuale
il candidato è l’elemento maggioritario, se
c’è una maggioranza.

Se io uso questo algoritmo su un pezzo di carta con AAACCBB come input, il candidato suggerito sarebbe diventato B ciò che è ovviamente sbagliato.

Per come la vedo io, ci sono due possibilità

  1. Gli autori non hanno mai provato il loro algoritmo su qualcosa che non AAACCBBCCCBCC, sono completamente incompetente e dovrebbe essere licenziato sul posto (altre).
  2. Sono chiaramente manca qualcosa, deve venire bannato da Stackoverflow e non essere mai consentito di toccare qualsiasi cosa che riguardi la logica.

Nota: Qui è un C++ implementazione dell’algoritmo da Niek Sanders. Io credo che correttamente implementato l’idea e come tale ha lo stesso problema (o no?).

 

5 Replies
  1. 45

    L’algoritmo funziona solo quando il set ha una maggioranza-più della metà degli elementi stessi. AAACCBB nel tuo esempio non ha la maggioranza. Il più frequente lettera si verifica 3 volte, la lunghezza della stringa è 7.

    • Succede a tutti. Non essere troppo severo, in svolgimento punto 2. dalla tua risposta 🙂
    • Mi ha preso un buon paio di minuti 😛
    • ok, Ora la vedo io. L’algoritmo stabilisce che “Questo algoritmo decide quale elemento di una sequenza è in maggioranza”. Trascurato la maggior parte al primo sguardo, e ha assunto la sua parlando di un elemento che appare numero massimo di volte. La maggior parte qui significa che l’elemento deve apparire almeno la metà il “numero di elementi:” i tempi !
    • Vuoi dire che “più della metà”, invece di “almeno la metà”.
  2. 27

    Piccolo, ma importante, oltre alle spiegazioni. Moore algoritmo di Voto ha 2 parti –

    1. prima parte dell’esecuzione di Moore algoritmo di Voto solo ti dà un candidato per la maggioranza elemento. Notare la parola “candidato” qui.

    2. Nella seconda parte, abbiamo bisogno di scorrere l’array, ancora una volta, per determinare se il candidato si verifica il massimo numero di volte (cioè maggiore dimensione/2 volte).

    Prima iterazione è quello di trovare il candidato, & la seconda iterazione è quello di verificare se questo elemento si verifica la maggior parte delle volte in una data matrice.

    Così il tempo è la complessità: O(n) + O(n) ≈ O(n)

    • +1 io stavo per scrivere sull’completamente trascurato il fatto che la seconda iterazione è necessario verificare che il candidato. Speriamo che l’OP si noterà questo ritardo di risposta.
    • +1 ho. Thx Srikar.
    • La spiegazione dell’autore stesso: cs.utexas.edu/users/moore/best-ideas/mjrty/index.html
    • Il passaggio 1 non darà Più Frequenti candidato. AAABBCC darà la C come candidato finale, ma non C è la più frequente e la maggioranza. Quindi si esegue il 2 ° passo per vedere la matrice ha nessuna maggioranza.
  3. 7

    Dal primo collegati domanda:

    con la proprietà che più della metà delle voci dell’array sono pari a N

    Da Boyer Moore pagina:

    quale elemento di una sequenza è in maggioranza, a condizione che vi sia un elemento

    Entrambi questi algoritmi in modo esplicito si supponga che un elemento si verifica almeno N/2 volte. (Si noti in particolare che la “maggioranza” non è la stessa come “la maggior parte dei comuni.”)

    • +1. Secondo vicino. Non posso credere che ho trascurato che. Grazie.
    • Siete i benvenuti 🙂 È facile confondere i due concetti!
  4. 0

    Ho scritto un codice C++ per questo algoritmo

    char find_more_than_half_shown_number(char* arr, int len){
    int i=0;
    std::vector<int> vec;
    while(i<len){
        if(vec.empty()){     
            vec.push_back(arr[i]);
            vec.push_back(1);
        }else if(vec[0]==arr[i]){ 
            vec[1]++;
        }else if(vec[0]!=arr[i]&&vec[1]!=0){
            vec[1]--;
        }else{                   
            vec[0]=arr[i];
        }
        i++;
    }
    int tmp_count=0;
    for(int i=0;i<len;i++){
        if(arr[i]==vec[0])
            tmp_count++;
    }
    if(tmp_count>=(len+1)/2)
        return vec[0];
    else
        return -1;
    }
    

    e la funzione principale è come di seguito:

    int main(int argc, const char * argv[])
    {
        char arr[]={'A','A','A','C','C','B','B','C','C','C','B','C','C'};
        int len=sizeof(arr)/sizeof(char);
        char rest_num=find_more_than_half_shown_number(arr,len);
        std::cout << "rest_num="<<rest_num<<std::endl;
        return 0;
    }
    
  5. 0

    Quando il test è “AAACCBB”, il set non ha la maggioranza. Perché nessun elemento si verifica più di 3 volte, in quanto la durata di “AAACCBB” 7.

    Ecco il codice per “il Boyer Moore e di Tempo Lineare Algoritmo di Voto”:

    int Voting(vector<int> &num) {
            int count = 0;
            int candidate;
    
            for(int i = 0; i < num.size(); ++i) {
                if(count == 0) {
                    candidate = num[i];
                    count = 1;
                }
                else
                    count = (candidate == num[i]) ? ++count : --count;
            }
            return candidate;
        }
    

Lascia un commento