Jak zliczyć z dwuwymiarowej tablicy najczęsciej wystepujący ciąg znaków

Odpowiedz Nowy wątek
2019-08-27 23:15
0

Zastanawiam się nad najszybszym i prostym algorytmem do zliczenia który wiersz znaków w tablicy występuje najczęściej ( możliwe znaki do wystąpienia a,b,c,d )
np:

a
abc
abcd
abc
aaa
b
b
aaabcd
abcd
abcd

tutaj najczęściej występuje wiersz abcd, i teraz załóżmy że mam długie ciągi znaków i więcej wierszy. Mój pomysł na chwile obecną to: zacząć od 1 znaku, jeśli po nim nie występują żadne nastepne znaki to zliczać ile jest a ile b ile c ile d i zostawiać ten najdłuższy z jednego znaku, przejść do wierszy gdzie wystepuje wiecej niż jeden znak i tak samo zliczać i później porównywać ile jest najwięcej z jednego znaku ile z dwóch znaków i dalej iść do wierszy składających się z 3 znaków. Macie lepszy pomysł? :D

Pozostało 580 znaków

2019-08-27 23:30
0

Posortuj i przechodząc tablicę licz ile jest takich samych.

Pozostało 580 znaków

2019-08-27 23:38
0

j.w. albo map<string, int>


░█░█░█░█░█░█░█░█░█░█░█░

Pozostało 580 znaków

2019-08-28 00:08
0

a jakie sortowanie byłoby najkorzystniejsze?

Pozostało 580 znaków

2019-08-28 00:11
0

@Michał Nadrocki: w C++ po prostu uzyj std::sort. Z reguly najszybsze bedzie quick sort ale w pesymistycznym przypadku heap sort bedzie lepsze (w C++ jesli dobrze pamietam to sort zacznie robic quick sorta, ale jak zauwazy ze jest pesymistyczny przypadek to zmieni na heap sort. Introsort chyba?).


░█░█░█░█░█░█░█░█░█░█░█░
edytowany 1x, ostatnio: krwq, 2019-08-28 00:12

Pozostało 580 znaków

2019-08-28 00:18
0

ok dzięki za pomoc ;) a przeczytałem, że jakieś bucket sort II ma złożoność czasową O(n) czy to jest to zaimplementowania?

Pozostało 580 znaków

2019-08-28 00:27
1

W tym przypadku unordered_map będzie trywialne i da ci też O(n). Iterujesz po danych i wrzucasz do mapy. Jeśli już taki wpis w mapie jest, to wpisujesz poprzednia_wartość+1, a jak jeszcze nie ma to wpisujesz z wartością 1.


Masz problem? Pisz na forum, nie do mnie. Nie masz problemów? Kup komputer...
edytowany 1x, ostatnio: Shalom, 2019-08-28 00:28
Czyli de facto bucket sort, ale bez sortowania ;) - hauleth 2019-08-28 10:31

Pozostało 580 znaków

2019-08-28 01:09
0

a jeśli chciałbym to zrobić bez użycia map? i dodam że sortowanie nie wchodzi w grę bo nie dodałem, że kolejność znaków ma znaczenie. abcb to jest co innego niż abbc

Sortowanie tablicy, a nie jej elementów. - lion137 2019-08-28 10:39

Pozostało 580 znaków

2019-08-28 10:36
1

Poczekaj, dla podanych przez Ciebie danych jaki powinien być wynik? Bo widzę, że jest coś zamotane. Bo z jednej strony mówisz, że chcesz liczyć ciągi znaków a potem mówisz coś o pojedynczych znakach. Zdecyduj się.

On próbuje coś w stylu RadixSorta zrobić chyba - Shalom 2019-08-28 11:10

Pozostało 580 znaków

2019-08-28 11:28
0

Naiwnie to będzie tak:

fun frequencies(xs):
    limit = length(xs)
    freq = [-1, -1, ...] limit times
    for i = 0 to limit - 1:
        count = 1
        for j = i + 1 to limit - 1:
            if xs[i] == xs[j]:
                count += 1
                freq[j] = 0
        if freq[i] != 0:
            freq[i] = count
    for i = 0 to limit - 1:
        if freq[i] != 0:
            print(xs[i] + " has frequency: " + freq[i])

Złożoność jest słaba O(n^2), lepiej użyć, jak sugerują powyżej, mapy, lub wbudowanych w język bibliotek: Collections.frequency w Javie, collections.Counter w Pythonie.


edytowany 2x, ostatnio: lion137, 2019-08-28 14:19

Pozostało 580 znaków

2019-08-28 11:29
0
Michał Nadrocki napisał(a):

a jeśli chciałbym to zrobić bez użycia map? i dodam że sortowanie nie wchodzi w grę bo nie dodałem, że kolejność znaków ma znaczenie. abcb to jest co innego niż abbc

Policz hash code dla każdego elementu, zachowaj na boku kopię X, posortuj te kody i zlicz najdłuższy ciąg takich samych kodów. Potem wykorzystaj kopię X w celu znalezienia ciągu znaków dla którego znalazłeś hash code.

Wada tego rozwiązania: trzeba policzyć hash code dla każdego ciągu w całości, nawet jeśli wszystkie różnią się np. na pierwszych 5 znakach.
Czyli złośliwy przypadek to będzie tablica losowych ciągów, każdy o długości zbliżonej lub większej niż liczba ciągów.


Szacuje się, że w Polsce brakuje 50 tys. programistów

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

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

Robot: CCBot