[Baczy]

Mam posortowaną tablicę o ilości n elementów. W jaki sposób wypisać najczęściej powtarzający się element, oraz ile razy się powtarza?

Dla przykładu:
2 7 5 2 3 2

wartość 2 powtarza się 3 razy

Może mi to ktoś w bardzo łopatologiczny sposób wyjaśnić?

#java #programowanie

[zwei]

Mam posortowaną tablicę

Dla przykładu:

2 7 5 2 3 2

@Baczy: coś chyba nie pykło

[Baczy]

@zwei: za słabo sprecyzowałem, wartości do tablicy są wpisywane losowo. Po wpisaniu elementów je sortuję.

[machoBear]

@Baczy: https://stackoverflow.com/questions/8545590/find-the-most-popular-element-in-int-array

[PanProgramista]

@Baczy: a po co to sortować? Wpisz każdą wartość jako indeks tablicy a wartość pod tym indeksem niech mówi ile razy dana liczba występuje. Czyli masz tablicę zer i przy dodawaniu tylko inkrementujesz odpowiedni indeks. Na końcu masz np.
Tab[2] = 3
Tab[7] = 1
Tab[5] = 1 itd.

[kszych]

@PanProgramista: ale wiesz że twoje rozwiązanie jest trochę "pamięciożerne"? ( ͡° ͜ʖ ͡°) przede wszystkim przed inicjalizacją tablicy musisz znać element max, jeśli będzie w #!$%@? duży to stworzysz tablicę xxxx elementową?

[PanProgramista]

@kszych: koleś pisze w javie, raczej pamięcią się nie przejmuje XD

[kszych]

@Baczy: jak tablica jest posortowana to zadanie jest proste: iterujesz po tablicy i sprawdzasz czy aktualny element jest taki sam jak poprzedni - jeśli jest, zwiększasz licznik. Jeśli natrafisz na "nowy" element, licznik zapisujesz jako dotychczasowy "max" i zaczynasz zliczać od nowa. Przy każdym "nowym" elemencie sprawdzasz czy licznik jest większy od dotychczas zapisanego maxa - jeśli jest, podmieniasz. W zasadzie złożoność jest liniowa, nie licząc sortowania, które przy quicksorcie jest

[63274682374]

@Baczy: zwróć uwagę, że na SO linkowanym przez @machoBear zaakceptowana odpowiedź nie jest najlepsza. Najlepiej przeczytaj cały wątek.

[sorhu]

@kszych
Najczęściej powtarzający się to nie to samo co największy.

[kszych]

@sorhu: no przecież pytanie jest o najczęściej powtarzający się

[63274682374]

@kszych: Wydaje mi się, że można ten algorytm zmikrooptymalizować wyrzucając licznik i przy nowym elemencie obliczać różnicę w indeksach tablicy pomiędzy pierwszym a ostatnim wystąpieniem danego elementu.
I dalej, przy każdym nowym znalezionym elemencie skakać z indeksem o dotychczasowy maxCount, sprawdzać czy nadal jest ten sam "nowy element". Jeśli tak, to iterujemy dalej, jeśli nie to szukamy początku nowego elementu.

[sorhu]

@kszych
Dobra, dupa, źle przeczytałem.

[glurp77]

@Baczy: może tak:

public Integer count(Integer[] arr) {

HashMap countingMap = new HashMap<>();

for (int i = 0; i < arr.length; i++) {
if (countingMap.containsKey(arr[i])) {
Integer oldValue = countingMap.get(arr[i]);
Integer newValue = ++oldValue;
countingMap.replace(arr[i], newValue);
} else {
countingMap.put(arr[i], 1);
}
}

Integer number = Collections.max(countingMap.entrySet(),Map.Entry.comparingByValue()).getKey();

return number;
}

[bladykiel]

Według mnie trochę zwięźlej i bardziej czytelnie ;P

private static int getMax(int array[]) {
Map map = new HashMap<>();
for (int i : array) {
Integer count = map.get(i);
map.put(i, count == null ? 1 : count + 1);
}
return Collections.max(map.entrySet(), Map.Entry.comparingByValue()).getKey();
}