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

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.

3

Albo źle opisałeś problem, albo przykład numer 2 jest błędny.

W opisie problemu zaznaczyłeś, że usuwamy elementy, które występują w tablicy przynajmniej 3 razy. Skoro w tablicy wyjściowej występuje 3 razy cyfra 3, to ja rozumiem, że ona też powinna zostać usunięta. Ewentualnie, może chodziło o to, że usuwasz pozycje, które w tablicy wejściowej występują 3 razy pod rząd, ale tego już nie napisałeś.

3
  • Oj to chyba nici z tego 300k w Google xD

  • Dla O(n^2):

  • szukasz sobie liniowo pierwszej grupy do usunięcia

  • usuwasz ją

  • następnie sprawdzasz wartość "przed" i "za" usuniętą grupą i jeśli są takie same to testujesz czy właśnie nie utworzyła ci się nowa grupa do usunięcia, jeśli tak to ją usuwasz i postępujesz dalej tak samo, jeśli nie, to znów liniowo szukasz kolejnej grupy do usunięcia

Idea jest taka że nie musisz sie nigdy "wracać" bo nowa grupa może powstać tylko na styku z grupą którą właśnie usunąłeś.

  • Jaka jest kolejność usuwania? Od lewej do prawej? Bo jest różnica np. dla 1110001 czy najpierw usunę 1 i dostanę 0001 i na koniec 1 czy najpierw usunę 0 i dostanę 1111 a potem pusty zbiór.
  • Wiesz jaka jest optymalna złożoność? Wydaje mi się że można by to zrobić w oparciu o strukturę zbiorów rozłącznych. Idea taka sama jak wyżej, tylko optymalizujemy to trochę w kontekście sprawdzania czy po połączeniu mamy nową grupę do usunięcia. Przelatujemy tablicę raz i powtarzające się liczby grupujemy w zbiory rozłączne O(n), mając jednocześnie pointer do zbioru który jest następnikiem i do poprzednika. Teraz przelatujemy przez tablicę jeszcze raz usuwając zbiory o liczności >=3 i jednocześnie takie usunięcie powoduje przepięcie naszego pointera na następnika do poporzednika i jeśli wartości w obu tych właśnie połączonych zbiorach są takie same to łączymy te sety (O(1)). To w sumie daje nam O(n).
0

Jakbyś Mógł posortować tablicę, to można już łatwo usunąć te elementy przechodząc ją liniowo (plus potrzebujemy jeszcze O(n) pamięci). Czyli, czasowo będzie nlog(n), pamięciowo O(n).

0

@Shalom: Masz moze kod do tego?
Wlasnie kolejnosc usuwania mnie zastanawia. Tak jakby brakowalo tej informacji w zadaniu. Raczej nie zakladam nic.

Optymalna zlozonosc to podobno lepiej niz n^2

0

Nie mam ale nie wygląda to na jakoś trudne do zaklepania. No a kolejność jest tu dość istotna, jak widać z przykładu który podałem ;]

0

To zadanie jest niekompletne. Bez podania kolejności usuwania to jest dla mnie niemożliwe do rozwiązania lepiej niż O(n^2). Szkoda czasy, lece dalej. Dzieki za pomoc. //TODO wrócić do tego po uzgodnieniu założeń

0
class DisjointSet:
    def __init__(self, prev, next, element, count):
        self.prev_set = prev
        self.next_set = next
        self.element = element
        self.count = count

    def join(self, another_set):
        if self.element == another_set.element:
            self.count += another_set.count
            self.next_set = another_set.next_set
            if another_set.next_set is not None:
                another_set.next_set.prev_set = self
        else:
            self.next_set = another_set
            another_set.prev_set = self

    def __repr__(self):
        return str([self.element] * self.count)


def create_sets(data):
    sets = [DisjointSet(None, None, 0, 0)]
    count = 1
    for i in range(len(data) - 1):
        if data[i] == data[i + 1]:
            count += 1
        else:
            new_set = DisjointSet(sets[-1], None, data[i], count)
            count = 1
            sets[-1].join(new_set)
            sets.append(new_set)
    return sets + [DisjointSet(None, None, 0, 0)]


def remove_repeating(data):
    sets = create_sets(data)
    print(sets)
    index = 1
    while index < len(sets):
        set_to_test = sets[index]
        if set_to_test.count >= 3:
            print("Removing set with element: %d and count: %d" % (set_to_test.element, set_to_test.count))
            sets.remove(set_to_test)
            set_to_test.prev_set.join(set_to_test.next_set)
            index -= 1
            if index < 0:
                index = 0
        else:
            index += 1
    return sets[1:-1]


def main():
    data = [1, 3, 3, 3, 2, 2, 2, 3, 1]
    data = [3, 1, 2, 2, 2, 1, 1, 1, 2, 2, 3, 1, 1, 2, 2, 2, 1, 1, 1, 2, 3]
    result = remove_repeating(data)
    print(result)


main()

Tak na szybko. Pewnie są tam jeszcze jakieś offbyone, ale wygląda sensownie. Niemniej opieram sie tu na zasadzie że usuwamy od lewej do prawej! Więc np. dla drugiego inputu który podawałeś wynik jest inny. Może kolejność usuwania ma być zależna od powtarzającego się elementu na przykład? Ale to nadal nie problem, bo zamiast iterować tak jak to zrobiłem, można przelecieć raz po tej mojej liście setów i zrobić sobie indeks który pamięta które sety są dla którego elementu i iterować w takiej kolejności.

0

W drugim przykładzie nie jest to ani "od lewej" ani "od prawej".
Ta kolejność wygląda jakby na początku szukało grup dwójek a potem reszty.

1

A może dasz linka do oryginalnego zadania. I popatrzymy na nie. Bo z tego co wkleiłeś wygląda że coś jest nie tak z założeniami, albo coś źle przykleiłeś.

0

Jasne:
Przekleiłem to z jakiejś platformy treningowej.

https://codeforces.com/blog/entry/67618

Właśnie przedarłem się przez komentarze i większość osób podkreśla brak podanych założeń jako problem z tym zadaniem.
Albo wszyscy się mylą i to jest do zrobienia sprytnym sposobem. Ale ja mam za małą głowę na to.

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ę.

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.

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

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.

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.

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 ;)

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 :)

0

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

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

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