Algoritm de împărțire și cucerire pentru găsirea elementului majoritar? (Programare, C++, Algoritm)

utilizator4652599 a intrebat.

Se spune că o matrice are un element majoritar dacă mai mult de jumătate din elementele sale sunt identice. Există un algoritm de tip divide et imperativ pentru a determina dacă un array are un element majoritar?

În mod normal, fac următoarele, dar nu se folosește divide-and-conquer. Nu vreau să folosesc Boyer-Moore algoritm.

int find(int[] arr, int size) {
    int count = 0, i, mElement;

    for (i = 0; i < size; i++) {
        if (count == 0) mElement = arr[i];

        if (arr[i] == mElement) count++;
        else count--;
    }

    count = 0;
    for (i = 0; i < size; i++) {
        if (arr[i] == mElement) count++;
    }

    if (count > size / 2) return mElement;
    return -1;
}

Comentarii

  • De ce nu vrei să folosești Boyer-Moore, este atât de eficient ? –  > Por Yves Daoust.
  • de fapt, vreau să o fac folosind algoritmul divide și cucerește, din acest motiv nu doresc să folosesc algoritmul Boyer-Moore – user4652599
  • Nu cred că este o idee atât de bună: dacă împărțiți matricea în două jumătăți, elementul cel mai frecvent poate să nu fie cel mai frecvent în cele două jumătăți. De exemplu, CCCAAAAABBBBBBBCCC. –  > Por Yves Daoust.
  • @YvesDaoust: Acest exemplu nu are un element majoritar (un element majoritar ar trebui să apară de cel puțin 9 ori din 16). –  > Por MSalters.
  • @MSalters: Aceeași restricție se aplică elementului majoritar: nu va fi majoritar în toate subdiviziunile și recurența D&Q nu este simplă. –  > Por Yves Daoust.
4 răspunsuri
Jerry Coffin

Pot vedea cel puțin o metodă de divizare și cucerire.

Începeți prin a găsi mediana, cum ar fi cu algoritmul Hoare’s Select. Dacă o valoare formează majoritatea elementelor, mediana trebuie să aibă acea valoare, deci tocmai am găsit valoarea pe care o căutăm.

De aici, găsiți (de exemplu) elementele percentilei 25 și 75. Din nou, dacă există un element majoritar, cel puțin unul dintre acestea ar trebui să aibă aceeași valoare ca și mediana.

Presupunând că nu ați exclus încă existența unui element majoritar, puteți continua căutarea. De exemplu, să presupunem că percentila 75 este egală cu mediana, dar percentila 25 nu este.

Când atunci continuați căutarea elementului aflat la jumătatea distanței dintre percentila 25 și mediană, precum și a celui aflat la jumătatea distanței dintre percentila 75 și final.

Continuați să găsiți mediana fiecărei partiții care trebuie să conțină sfârșitul elementelor cu aceeași valoare ca și mediana până când ați confirmat sau infirmat existența unui element majoritar.

Ca o paranteză: nu prea văd cum ar putea fi folosit Boyer-Moore pentru această sarcină. Boyer-Moore este o modalitate de a găsi un subșir într-un șir de caractere.

Comentarii

halfflat

Există, și nu necesită ca elementele să aibă o ordine.

Pentru a fi formali, avem de-a face cu multietaje (denumite și saci.) În cele ce urmează, pentru un multiansamblu S, , fie:

  • v(e,S) să fie multiplicitatea unui element e în S, , adică numărul de apariții ale acestuia (multiplicitatea este zero dacă e nu face parte din S deloc).
  • #S să fie cardinalitatea lui S, , adică numărul de elemente din S numărând multiplicitatea.
  • ⊕ să fie suma multiansamblurilor: dacă S = LR atunci S conține toate elementele din L și R numărând multiplicitatea, și anume v(e;S) = v(e;L) + v(e;R) pentru orice element e. (Aceasta arată, de asemenea, că multiplicitatea poate fi calculată prin „divide et impera”).
  • [x] să fie cel mai mare număr întreg mai mic sau egal cu x.

Elementul majoritar m din S, , dacă există, este acel element astfel încât 2 v(m;S) > #S.

Să numim L și R a divizare a S dacă LR = S și un divizare pară dacă |#L#R| ≤ 1. Altfel spus, dacă n=#S este par, L și R au exact jumătate din elementele lui S, și dacă n este impară, atunci una dintre ele are cardinalitatea [n/2], iar celălalt are cardinalitatea [n/2]+1.

Pentru o împărțire arbitrară a S în L și R, , două observații:

  1. În cazul în care niciuna dintre cele două L nici R are un element majoritar, atunci S nu poate: pentru orice element e, , 2 v(e;S) = 2 v(e;L) + 2 v(e;R) ≤ #L + #R = #S.

  2. Dacă unul dintre L și R are un element majoritar m cu multiplicitatea k, atunci acesta este elementul majoritar al S numai dacă are multiplicitatea r în cealaltă jumătate, cu 2(k+r) > #S.

Algoritmul majoritar(S) de mai jos returnează fie o pereche (m,k), indicând că m este elementul majoritar cu k apariții, sau niciunul:

  1. Dacă S este gol, se returnează none; dacă S are doar un singur element m, , atunci return (m,1). În caz contrar:
  2. Se face o împărțire pară a S în două jumătăți L și R.
  3. Fie (m,k) = majoritatea(L), dacă nu niciunul:

    a. Fie k’ = k + v(m;R).

    b. Return (m,k’) dacă 2 k’ > n.

  4. În caz contrar, să fie (m,k) = majoritatea(R), dacă nu niciunul:

    a. Fie k’ = k + v(m;L).

    b. Întoarcerea (m,k’) dacă 2 k’ > n.

  5. În caz contrar se returnează niciunul.

Rețineți că algoritmul este în continuare corect chiar dacă împărțirea nu este una pară. Cu toate acestea, este probabil ca împărțirea paritară să aibă rezultate mai bune în practică.

Addenda

Cazul terminal a fost explicitat în descrierea algoritmului de mai sus. Câteva exemple de cod C++:

struct majority_t {
    int m; // majority element
    size_t k; // multiplicity of m; zero => no majority element

    constexpr majority_t(): m(0), k(0) {}
    constexpr majority_t(int m_,size_t k_): m(m_), k(k_) {}

    explicit operator bool() const { return k>0; }
};

static constexpr majority_t no_majority;

size_t multiplicity(int x,const int *arr,size_t n) {
    if (n==0) return 0;
    else if (n==1) return arr[0]==x?1:0;

    size_t r=n/2;
    return multiplicity(x,arr,r)+multiplicity(x,arr+r,n-r);
}

majority_t majority(const int *arr,size_t n) {
    if (n==0) return no_majority;
    else if (n==1) return majority_t(arr[0],1);

    size_t r=n/2;
    majority_t left=majority(arr,r);
    if (left) {
        left.k+=multiplicity(left.m,arr+r,n-r);
        if (left.k>r) return left;
    }

    majority_t right=majority(arr+r,n-r);
    if (right) {
        right.k+=multiplicity(right.m,arr,r);
        if (right.k>r) return right;
    }

    return no_majority;
}

Comentarii

  • [x] este funcția floor? – utilizator1084944
  • [x] este funcția floor; și numărul de m funcția poate fi realizată și prin divide și cucerește: count ( m , LR ) = count ( m, , L ) + numărătoare ( m, , R), unde ⊕ reprezintă suma multiansamblurilor. (Voi edita răspunsul pentru a face acest lucru mai clar.) –  > Por halfflat.
ysrhung

Un algoritm mai simplu de împărțire și cucerire funcționează pentru cazul în care există mai mult de 1/2 elemente care sunt identice și există n = 2^k elemente pentru un oarecare număr întreg k.

FindMost(A, startIndex, endIndex)
{  // input array A

if (startIndex == endIndex)  // base case
        return A[startIndex]; 
x = FindMost(A, startIndex, (startIndex + endIndex - 1)/2);
y = FindMost(A, (startIndex + endIndex - 1)/2 + 1, endIndex);

if (x == null && y == null) 
    return null;
else if (x == null && y != null) 
    return y;
else if (x != null && y == null) 
    return x;
else if (x != y) 
    return null;
else return x

}

Acest algoritm ar putea fi modificat astfel încât să funcționeze pentru n care nu este exponent de 2, dar cazurile limită trebuie tratate cu atenție.

Comentarii

  • Dimensiune : 4 , Array : 1 2 3 1, încă returnează 1 când ar trebui să returneze null –  > Por Sparker0i.
Sandeep

Să spunem că array-ul este 1, 2, 1, 1, 1, 3, 1, 4, 1, 1, 6, 1.

Dacă o matrice conține mai mult de jumătate din elemente identice, atunci ar trebui să existe o poziție în care cele două elemente consecutive să fie identice.

În exemplul de mai sus, observați că 1 se repetă de mai mult de jumătate de ori. Iar indicii (indicele începe de la 0), indicele 2 și indicele 3 au același element.

Tags:,