Usuń z tablicy elementy powtarzające się co najmniej trzy razy.

Odpowiedz Nowy wątek
2019-08-17 09:29
0

Mając tablice znaków (cyfr), zwróć tablice po usunięciu elementów powtarzających się co najmniej trzy razy.

input: [1, 3, 3, 3, 2, 2, 2, 3, 1]
return: [1, 1] // To nie błąd, na początku usuwam dwójki, "łączę" to co zostało po ich usunięciu, następnie usuwam trójki.

input: [3,1,2,2,2,1,1,1,2,2,3,1,1,2,2,2,1,1,1,2,3]
return [3,1,3,2,3]

imput: [1, 3, 3, 3, 2, 2, 2, 1, 3]
return: [1, 1, 3]

Jaki algorytm miałby tu zastosowanie. Trudzę się nad O(n^3), nie mogę wymyślić nic O(n^2), co dopiero mówiąc o optymalnym rozwiązaniu.

edytowany 1x, ostatnio: InterruptedException, 2019-08-17 11:25
w pierwszym inpucie nie mialo byc 1,3,3,2,2,2,3,1 -> tak żeby nie było 3 trójek na starcie? - amd 2019-08-17 10:46
Zadanie nie jest chyba dobrze sformułowane bo prawdopodobnie chodzi o wynikowy najkrótszy ciąg. Tak przynajmniej wynika z przykładów. - twoj_stary_pijany 2019-08-17 12:53

Pozostało 580 znaków

2019-08-17 12:16
amd
0

Ehh, to jest zadanie nie z jakiejś stronki tylko z komentarza jakiejś prywatnej osoby. Szkoda czasu tracić na coś takiego. Pewnie koleś źle zapamiętał.
Lepiej porozwiązuj sobie zadania ze stronek co mają sprawdzarkę.

Pozostało 580 znaków

2019-08-17 12:18
0

Również mam takie wrażenie. Ale zakładając że tu nie ma nic do dopowiedzenia, to wychodzi że to wcale nie jest trywialne zadanie.
Jeszcze skonsultuje to z kilkoma osobami które zjadły zęby na algorytmach i napiszę wnioski.

Pozostało 580 znaków

2019-08-17 12:19
0

skonsultuje to z kilkoma osobami które zjadły zęby na algorytmach

No tak, bo przecież wiedza takiego @shalom to się na bubble-sort kończy, lepiej pogadać z prawdziwym fachowcę i ekspertę :D


That game of life is hard to play
I'm gonna lose it anyway
The losing card I'll someday lay
So this is all I have to say
edytowany 2x, ostatnio: cerrato, 2019-08-17 12:20
Shalom ma jeszcze zęby? To się nie nadaje :D - Delor 2019-08-17 12:35
no o tym nie pomyślałem ;) - cerrato 2019-08-17 12:50

Pozostało 580 znaków

2019-08-17 12:50
0

input: [3,1,2,2,2,1,1,1,2,2,3,1,1,2,2,2,1,1,1,2,3]
return [3,1,3,2,3]

input: [3,1,2,2,2,1,1,1,2,2,3,1,1,2,2,2,1,1,1,2,3]
input: [3,1,2,2,2,1,1,1,2,2,3,1,1,1,1,1,2,3]
input: [3,1,2,2,2,1,1,1,2,2,3,2,3]
input: [3,1,2,2,2,2,2,3,2,3]
input: [3,1,3,2,3]

@Shalom: Czy Twoje rozwiązanie nie usunie zbyt wcześnie tych pierwszych dwójek?

Nie wiem czy przypadkiem nie trzeba tutaj sprawdzić wszystkich kombinacji usunięć i wybrać najkrótszy wynikowy ciąg.

edytowany 1x, ostatnio: twoj_stary_pijany, 2019-08-17 12:54
Pisałem że to zależy od tego w jakiej kolejności mamy usuwać :) Ale jeśli celem jest najkrótszy wynikowy ciąg to mam wątpliwości czy da się to zrobić w jakiejś niskiej złożoności. - Shalom 2019-08-17 12:55
Przykłady tak sugerują. - twoj_stary_pijany 2019-08-17 12:56

Pozostało 580 znaków

2019-08-17 13:01
0

Nie wiem czy Twój algorytm zadziała dla sytuacji 0111002220 - po skasowaniu grupy 111 lub 222 nie należy od razu kasować 000. Ten problem nie ma własności optymalnej podstruktury, więc nie da się tego również ogarnąć algorytmem dynamicznym, co dałoby złożoność O(N^2). Oczywiście to implikacja w jedną stronę, może istnieje jakiś algorytm IQ 200 (grafy, przepływy?), który umie to zrobić zakładanym czasie.

Pozostało 580 znaków

2019-08-17 13:08
0

@Charles_Ray: wprawdzie masz rację, ale wydaje mi się, że trochę sobie dopowiadasz. Zwróć uwagę, że w opisie zadania (a przynajmniej w wersji przedstawionej przez autora wątku) jest jedynie mowa o tym, żeby usuwać powtarzające się liczby i nie ma nigdzie informacji o tym, żeby optymalizować usuwanie liczb w ten sposób, aby ciąg wyjściowy był jak najkrótszy. Twoja uwaga jest trafna, ale nie ma związku z tematem tego wątku. Tak mi się przynajmniej wydaje, ale ja nie jestem kimś, kto stracił zęby na algorytmach ;)


That game of life is hard to play
I'm gonna lose it anyway
The losing card I'll someday lay
So this is all I have to say
Pokaż pozostałe 5 komentarzy
Jakich 3? Musisz ściagnąć wszystkie pasujące, a możesz zacząć ściągać dopiero jak trafisz na inny element do położenia. Nie możesz zacząć zdejmować od razu jak trafisz na 3. Przecież jak masz 4 jedynki inputu to masz ściągnać wszyskie 4 a nie ściągnąć 3 a potem ci zostanie jedna. Więc w twoim przypadku jeśli inputem są same 1 to musisz polożyć na stosie wszystkie O(n) a potem zdejmować je znów O(n). - Shalom 2019-08-17 13:34
Musiałbyś, tak jak w moim algorytmie, pamiętać ile elementów tego typu masz na stosie i zdejmować je "na raz" i w sumie dojdziesz zaraz do tego samego do czego ja doszedłem ;] - Shalom 2019-08-17 13:37
W zasadzie racja, ale mój algorytm jest w zasadzie trywialny i zapiszesz go w 5 linijkach. A w Twoim musisz robić masę lookupów w obu kierunkach :) - twoj_stary_pijany 2019-08-17 13:38
Nie zapiszesz w 5 bo corner case masz, tak samo jak u mnie :P Musisz sprawdzać czy nie wychodzisz "poza stos", musisz sprawdzać czy trafiłeś na inną liczbę w inpucie / na koniec inputut ;) - Shalom 2019-08-17 13:41

Pozostało 580 znaków

2019-08-17 14:05
0

@Shalom:

def solution(sequence, stack = [], next = -1, leader = -1):
    if (len(stack) >= 3 and stack[-1] == stack[-2] == stack[-3] and next is not stack[-1]):
        while stack[-1] == leader: stack.pop()
    return stack if not sequence else solution(sequence[1:], stack + [sequence[0]], sequence[1] if len(sequence) > 1 else -1, sequence[0])

Dla testu [1, 3, 3, 3, 2, 2, 2, 3, 1] zwraca [1, 3, 1]. Nie chce mi się dalej testować, ale jest 5 linijek :)
Edit: Pomyliłem się, są 4 linijki bo while można zapisać w jednej linijce :)

edytowany 3x, ostatnio: twoj_stary_pijany, 2019-08-17 14:08
Przecież rozwiązaniem jest ciąg długości 2. Chyba, że ja rozwiązuje inne zadanie :) - Charles_Ray 2019-08-17 14:36
Jeżeli tak jest to wtedy prawdopodobnie chodzi o najkrótszy ciąg i to jest trudniejszy problem. O tym też pisałem wcześniej. - twoj_stary_pijany 2019-08-17 14:42

Pozostało 580 znaków

2019-08-17 14:28
0

@cerrato: no jak nie jak tak: https://codeforces.com/blog/entry/67618

Wynikowy ciąg ma być możliwie najkrótszy.

Nie wynika to z pierwszegp posta :p - cerrato 2019-08-17 15:44

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

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