zliczanie wystąpień

0

Witam

Koledzy kminię nad napisaniem wydajnego algorytmu zliczającego wystąpienia w tablicy.

Mam tablicę:
char[] tab = new char[10];

Jest ona wypełniona liczbami losowymi.

Funkcja, której szukam ma zwracać liczbę, która powtórzyła się najwięcej razy. Jeśli jest więcej liczb o takiej samej ilości wystąpień - dowolna z nich może zostać zwrócona.
Chodzi o to żeby ten algorytm był wydajny. Sam napisałem jakieś wypociny, ale strasznie długi, brzydki kod.

Jakieś pomysły, sugestie?

0

Jeśli losujesz liczby z niewielkiego zakresu wystarczy zwykłe zliczanie, a algorytm będzie miał złożoność liniową, jeśli zakres będzie zbyt duży na zliczanie najlepiej będzie posortować tablicę i sprawdzić w pętli, która liczba powtórzyła się najwięcej razy i masz algorytm O(n log n), gdzie n=rozmiar tablicy.

0

Jakieś pomysły na zliczanie bez sortowania i z sortowaniem?

0

A może zrób HashMapę mapującą liczby na ilość ich wystąpień, a potem przeleć całą mapę w celu znalezienia największej wartości.

package Main;

import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;

public class Main {

    public static void main(String[] args) {
        // tablica wejściowa
        byte[] tablicaBajtów = new byte[] { 5, 5, 6, 6, 6, 7 };
        // mapa pomocnicza
        Map<Integer, Integer> mapa = new HashMap<Integer, Integer>();
        // zliczanie wystąpień dla każdej wartośći
        for (byte bajt : tablicaBajtów) {
            if (mapa.containsKey(Integer.valueOf(bajt))) {
                Integer wartość = mapa.get(Integer.valueOf(bajt));
                mapa.put(Integer.valueOf(bajt), wartość + 1);
            } else {
                mapa.put(Integer.valueOf(bajt), 1);
            }
        }
        // szukanie najczęściej występującej wartośći
        Map.Entry<Integer, Integer> maxEntry = null;
        for (Entry<Integer, Integer> entry : mapa.entrySet()) {
            if (maxEntry == null || entry.getValue() > maxEntry.getValue()) {
                maxEntry = entry;
            }
        }
        // wypisanie najczęściej występującej wartości
        System.out.println(maxEntry.getKey());
    }
}

Co prawda dość pamięciożerne.

Z sortowaniem może być tak:

package Main;

import java.util.Arrays;

public class Main {

    public static void main(String[] args) {
        byte[] tablicaBajtów = new byte[]{5, 5, 6, 6, 6, 7};
        Arrays.sort(tablicaBajtów);
        int maksPowtórzeń = 0;
        int najczęstszaWartość = 0;
        {
            int ostatniaWartość = tablicaBajtów[0];
            int powtórzeńOstatniej = 0;
            for (int i = 0; i < tablicaBajtów.length; i++) {
                if (tablicaBajtów[i] == ostatniaWartość) {
                    powtórzeńOstatniej++;
                } else {
                    powtórzeńOstatniej = 1;
                    ostatniaWartość = tablicaBajtów[i];
                }
                if (powtórzeńOstatniej > maksPowtórzeń) {
                    maksPowtórzeń = powtórzeńOstatniej;
                    najczęstszaWartość = ostatniaWartość;
                }
            }
        }
        System.out.println(najczęstszaWartość);
    }
}
0

Proponuje poprawke:

        (...)
        Integer maxValue = ... ; // odpowiednia inicjalizacja
        for (Integer value : mapa.values()) { // albo valueSet() - nie pamietam, pisane z pamieci
            if (value > maxValue) {
                maxValue = value;
            }
        }
        // wypisanie najczęściej występującej wartości
        ...
0

Ja proponuję tylko nieco skrócić:

Arrays.sort(tablica);

int powtórzeńOstatniej = 0;
int powtórzeń = 0;
int najczęstszaWartość = tablica[0];

for (int i = 1; i < tablica.length; i++) {
    if (tablica[i] == tablica[i - 1]) {
        powtórzeń++;
    } else {
        if (powtórzeń > powtórzeńOstatniej) {
            najczęstszaWartość = tablica[i - 1];
            powtórzeńOstatniej = powtórzeń;
        }
        powtórzeń = 0;
    }
}

return najczęstszaWartość;

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0