Nie słyszałem o czymś takim jak "przywódca ciągu". Ale ja się na algorytmach dobrze nie znam, może dlatego. W każdym razie znalazłem coś takiego; cytat:
Przywódcą ciągu jest element, który występuje w ciągu więcej razy niż połowa długości tego ciągu.
Czyli uwzględniając to, co napisałaś, to dla ciągu o długości n:
- "przywódcą I rzędu" jest element występujący więcej niż
n/2 razy; inaczej mówiąc, jeśli liczbę wystąpień "przywódcy I rzędu" oznaczymy przez k1, to k1 = n/2;
- "przywódcą II rzędu" jest element występujący więcej niż
n/3 razy; inaczej mówiąc, jeśli liczbę wystąpień "przywódcy II rzędu" oznaczymy przez k2, to k2 = n/3.
Nie jestem pewien, czy "przywódca II rzędu" może być także "przywódcą I rzędu". Zakładam, że nie. Czyli że spełniony musi być dodatkowy warunek dla "przywódcy II rzędu": występuje mniej niż lub dokładnie n/2 razy.
W związku z tym pseudokod rekurencyjny mógłby tak wyglądać:
find_counts (arr, cur, res)
if equal(cur, length(arr))
then return res
else
elem <- find_index(res, x => equal(x[0], arr[cur]))
if equal(elem, NULL)
then // Nie znaleziono elementu; czyli - jest on nowy
return find_counts(arr, cur + 1, concat(res, [arr[cur], 1]))
else // Znaleziono element; czyli - zwiększ jego częstość występowania
return find_counts(
arr,
cur + 1,
concat(
subarr(res, elem - 1),
[res[elem][0], res[elem][1] + 1],
subarr(elem + 1, res)
)
)
find_all_second_leaders (arr, size, cur, res)
if equal(cur, length(arr))
then return res
else
if greater(arr[cur][1], size/3) and lessOrEqual(arr[cur][1], size/2)
then // Przywódca II rzędu
return find_all_second_leaders(arr, size, cur + 1, concat(res, arr[cur][0]))
else // Idźmy dalej - to nie przywódca II rzędu
return find_all_second_leaders(arr, size, cur + 1, res)
Żeby nie było, że nie przetestowałem, to przetestowałem. Nadal to tylko 1 test, więc mogą być błędy w tym algorytmie. O tak to wygląda w JavaScripcie:
const find_counts
= (arr, cur, res) => {
if (cur === arr.length) {
return res;
} else {
const elem = res.findIndex(x => x[0] === arr[cur]);
return elem === -1
? find_counts(arr, cur + 1, res.concat([[arr[cur], 1]]))
: find_counts(arr, cur + 1, [...res.slice(0, elem), [res[elem][0], res[elem][1] + 1], ...res.slice(elem + 1, res.length)]);
}
};
const find_all_second_leaders
= (arr, size, cur, res) => {
if (cur === arr.length) {
return res;
} else {
if (arr[cur][1] > size/3 && arr[cur][1] <= size/2) {
return find_all_second_leaders(arr, size, cur + 1, res.concat(arr[cur][0]));
} else {
return find_all_second_leaders(arr, size, cur + 1, res);
}
}
};
const arr = [1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3];
const counts = find_counts(arr, 0, []);
console.log('counts:',counts.map(x => `(${x[0]}, ${x[1]})`)); // Wypisuje: counts: (1, 1),(2, 5),(3, 8)
const leaders = find_all_second_leaders(counts, arr.length, 0, []);
console.log('leaders:',leaders); // Wypisuje: leaders: 2
UPDATE: Poprawiłem niepoprawne counts w pseudokodzie find_all_second_leaders na poprawne arr.
UPDATE2: Spróbowałem trochę poprawić czytelność pseukodu rozbijając ostatnie rekurencyjne wywołanie funkcji find_counts na kilka linii (przedtem było w jednej).
UPDATE3: Zmieniłem nazwę null na NULL, żeby bardziej się odróżniała od nazw zmiennych (NULL to jednak stała – jeśli w ogóle tak klasyfikować – a nie zmienna).