Nu exista diferente intre titluri.
Diferente intre continut:
h3. Soluţie O(n log{~2~}n)
O altă soluţie care ar permite numărarea eficientă a numărului de apariţii a unui element în acest şir ar fi să sortăm şirul pentru că apoi elementele egale vor fi în poziţii consecutive.
O altă soluţie care ar permite numărarea eficientă a numărului de apariţii al unui element în acest şir ar fi să sortăm şirul pentru că apoi elementele egale vor fi în poziţii consecutive.
== code(cpp) |
int sortMajority(int n, int[] a) {
h3. Soluţie O(n) cu 'statistici de ordine':problema/sdo
O idee ce ne vine pe urma acestei rezolvări este aceea că în şirul sortat, un element majoritar se va afla în şirul sortat şi pe poziţia $n/2$. Ştim că există algoritmi de selecţie care ne găsesc elemente de poziţie o fixată $k$ din şirul sortat în complexitate $O(n)$. Astfel vom găsi mai întâi elementul de pe poziţia $n/2$ iar apoi vom verifica dacă acesta este elementul majoritar al şirului. Astfel avem o soluţie de complexitate $O(n)$ iar şirul iniţial va fi modificat. Există metode de selecţie nerandomizate, dar pentru uşurinţa implementării vom folosi una randomizată.
O idee ce ne vine pe urma acestei rezolvări este aceea că în şirul sortat, un element majoritar se va afla în şirul sortat şi pe poziţia $n/2$. Ştim că există algoritmi de selecţie care ne găsesc elemente de o poziţie fixată $k$ din şirul sortat în complexitate $O(n)$. Astfel, vom găsi întâi elementul de pe poziţia $n/2$ iar apoi vom verifica dacă acesta este elementul majoritar al şirului. Astfel avem o soluţie de complexitate $O(n)$ iar şirul iniţial va fi modificat. Există metode de selecţie nerandomizate, dar pentru uşurinţa implementării vom folosi una randomizată.
== code(cpp) |
int select(int n, int[] a, int left, int right, int k) {
h3. Soluţie O(n)
Un ultim algoritm şi cel mai eficient dintre cele prezentate apare în lucrarea $[1]$ şi probabil acesta este cunoscut cititorilor. Autorii au un mod plastic de a prezenta algoritmul:
Un ultim algoritm şi cel mai eficient dintre cele prezentate apare în lucrarea [1] şi probabil acesta este cunoscut cititorilor. Autorii au un mod plastic de a prezenta algoritmul:
„Imaginaţi-vă o sală de conferinţă în care votanţii ţin fiecare o placă ce poartă numele candidatului preferat. Să presupunem că se ajunge la o bătaie generală în care votanţii cu convingeri diferite încep să se lovească reciproc cu plăcile. Să mai presupunem că fiecare votant care pune la pământ un membru cu alte convingeri este simultan şi el pus la pământ de adversar. Este evident că dacă ar fi vreun candidat care are mai multe voturi decât toate voturile celorlalţi candidaţi, atunci această luptă va fi câştigată de acest candidat şi la dispariţia haosului din urma luptei, votanţii ce au rămas în picioare vor fi susţinători ai candidatului amintit. În caz că nu există o majoritate clară pentru un candidat sau altul, la finalul luptei rămân în picioare votanţi care susţin acelaşi candidat, dar acesta poate să nu fie reprezentantul majorităţii. Deci, în general, dacă cineva rămâne în picioare, preşedintele conferinţei este obligat să verifice dacă într-adevar candidatul întruneşte votul a jumătate plus unu din votanţi. Algoritmul practic folosit de noi va fi un fel de joc al împerecherilor între candidaţi de opinii diferite până când toţi votanţii rămaşi necuplaţi vor susţine acelaşi candidat.”
Realizăm acest algoritm parcurgând lista votanţilor şi ţinând un contor cu numărul de candidaţi $k$ neîmperecheaţi până la pasul curent, evident dacă ei sunt neîmperecheaţi trebuie să susţină acelaşi candidat cand pentru că altfel am fi putut să cuplăm câţiva dintre ei.
Realizăm acest algoritm parcurgând lista votanţilor şi ţinând un contor cu numărul de candidaţi $k$ neîmperecheaţi până la pasul curent, evident dacă ei sunt neîmperecheaţi trebuie să susţină acelaşi candidat pentru că altfel am fi putut să cuplăm câţiva dintre ei.
Menţionăm că această rezolvare are doar operaţii în care se verifică dacă două valori sunt identice, fapt ce se poate dovedi util pentru obiecte complexe care ar substitui candidaţii din problemă. Rezolvările anterioare s-au folosit de faptul că între elementele şirului ar exista o relaţie de ordine sau că am putea efectua asupra lor operaţii aritmetice.
== code(cpp) |
bq. Se dă un şir de $n$ numere naturale şi un număr întreg $k$, se cere determinarea tuturor elementelor care apar de cel puţin $[n/k]+1$ ori în şir.
h3. Soluţii ?
h3. Soluţii O(n*k)
Primele trei rezolvări prezentate pentru problema iniţială pot fi evident generalizate şi folosite şi pentru această problemă. Generalizarea abordării care implica folosirea cifrelor pentru a rezolva noua problemă pare imposibilă. Vom vorbi mai departe de două din celelalte trei abordări.
int[] cand = new int[k - 1], notMatched = new int[k - 1], num = new int[k-1];
Arrays.fill(cand, -1);
int num = 0;
//faza de cuplare
// cuplare
for (int i = 0; i < n; i++) {
boolean found = false;
for (int j = 0; j < k - 1; j++) {
if (cand[j]==a[i]) {
notMatched[j]++;
found = true;
break;
boolean found = false;
for (int j = 0; j < k - 1; j++) {
if (cand[j] == a[i]) {
notMatched[j]++;
found = true;
break;
}
}
if (!found) {
for (int j = 0; j < k - 1; j++) {
if (notMatched[j] == 0) {
cand[j] = a[i];
notMatched[j] = 1;
found = true;
break;
}
}
if (!found) {
for (int j = 0; j < k - 1; j++) {
if (notMatched[j]==0) {
cand[j] = a[i];
notMatched[j] = 1;
found = true;
break;
}
}
if (!found) {
for (int j = 0; j < k – 1; j++) notMatched[j]--;
}
}
}
if (!found) {
for (int j = 0; j < k – 1; j++) notMatched[j]--;
}
}
}
//faza de verificare
// verificare
for (int i = 0; i < n; i++) {
for (int j = 0; j < k - 1; j++) {
if (a[i]==cand[j] && notMatched[j] != 0) num[j]++;
}
for (int j = 0; j < k - 1; j++) {
if (a[i] == cand[j] && notMatched[j] != 0) num[j]++;
}
}
int numMaj = 0;
for (int j = 0; j < k - 1; j++) {
if (num[j] > n/k) numMaj++;
if (num[j] > n/k) numMaj++;
}
int[] ret = new int[numMaj];
numMaj = 0;
for (int j = 0; j < k - 1; j++) {
if (num[j] > n/k) {
ret[numMaj] = cand[j];
numMaj++;
}
if (num[j] > n/k) {
ret[numMaj] = cand[j];
numMaj++;
}
}
return ret;
Nu exista diferente intre securitate.
Topicul de forum nu a fost schimbat.
