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 10:01
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ś.


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

Pozostało 580 znaków

2019-08-17 10:24
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).

Masz problem? Pisz na forum, nie do mnie. Nie masz problemów? Kup komputer...
Wydaje mi się, że to nie jest poprawne optymalne rozwiązanie. Ale musiałbym mieć kod żeby przetestować. Dzięki za pomoc. - InterruptedException 2019-08-17 11:29

Pozostało 580 znaków

2019-08-17 10:58
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).


edytowany 1x, ostatnio: lion137, 2019-08-17 10:58
No chyba nie o_O. Przecież jak masz 11001100 to nie usuniesz nic, a twoją metodą usuniesz wszystko? - Shalom 2019-08-17 11:07
To właśnie trzeba dopracować:) - lion137 2019-08-17 13:09

Pozostało 580 znaków

2019-08-17 11:09
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

Pozostało 580 znaków

2019-08-17 11:10
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 ;]


Masz problem? Pisz na forum, nie do mnie. Nie masz problemów? Kup komputer...

Pozostało 580 znaków

2019-08-17 11:27
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ń

Pozostało 580 znaków

2019-08-17 11:35
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.


Masz problem? Pisz na forum, nie do mnie. Nie masz problemów? Kup komputer...
edytowany 1x, ostatnio: Shalom, 2019-08-17 11:37
Dla 3-ciego też jest inny. To zadanie to jakieś troll zadanie. Szkoda czasu na to panowie i panie. - InterruptedException 2019-08-17 11:44
To po co Wrzucasz na forum i Zajmujesz ludziom czas? - lion137 2019-08-17 11:56

Pozostało 580 znaków

2019-08-17 11:35
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.

Możliwe że szuka np. najpierw 1, potem 2, potem 3... - Shalom 2019-08-17 11:41
Nie. To nie jest kolejność 1->2->3 (drugi przykład nie pasuje). Nie jest ot też kolejność odwrotna (pierwszy przykład). Zaczyna od dwójek. - Delor 2019-08-17 11:43

Pozostało 580 znaków

2019-08-17 12:06
amd
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ś.

edytowany 1x, ostatnio: amd, 2019-08-17 12:15

Pozostało 580 znaków

2019-08-17 12:11
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.

edytowany 1x, ostatnio: InterruptedException, 2019-08-17 12:12

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