Witam,
muszę napisać program wyszukujący w czasie liniowym O(n) w tablicy jednowymiarowej parę liczb i przypisanie ich do zmienych pozA oraz pozB.
np:
z tablicy 2,1,2,4,5,5,6,4
ma mi zapisać dla wartości 2 do zmiennej pozA=1 , pozB=3
następnie dla wartości 5 pozA=5, pozB=6
i tak w pętli dalej.
zapewne należy tutaj zastosować tablicę list
ale nie wiem jak się za to zabrac.
Pomoże ktoś ?
Jakiś algorytm krotkowy cokolwiek ?
z góry dziękuję
Nie bardzo rozumiem gdzie jest problem. Lecisz liniowo po danych i ładujesz je do HashMapy int->list<int> gdzie kluczem jest liczba a wartością jest lista pozycji na których występuje ta liczba.
from collections import defaultdict
data = [2,1,2,4,5,5,6,4]
map = defaultdict(list)
for index, number in enumerate(data):
map[number].append(index)
for number, positions in map.items():
print(number, positions)
Jako że ty sobie chyba chcesz indeksować od 1 a nie od 0 to musisz wrzucać do listy index+1 ale to szczegół.
okej dzięki za odpowiedź, ale nie przejdzie...
Muszę zastosować pomocniczą tablice Tab oraz zmienne pozA oraz pozB.
akurat jak to wykładowca zaznaczył ma być zgodne z wytycznymi bez odchyleń.
aczkolwiek ten kod się mi przyda do innego zadania.
Realizacja w Cpp
Nie bardzo cię rozumiem. Jak najbardziej zastosowałem tu pomocniczą tablicę, chociaż użyłem mapy dla wygody. Ale mapa z kluczem który jest intem to jest tablica właśnie. Dodatkowo dla wygody zapisywałem sobie te liczby w liście a nie w strukturze z dwoma polami, ale to jest przecież żadna różnica. Ten kod to jest dokładnie to czego potrzebujesz, musisz go tylko trochę "popsuć" jeśli masz takie śmieszne wytyczne. Ale idea będzie dokładnie ta sama.
równie dobrze możesz posortować przez zliczanie, zapamiętując poprzednie pozycje elementów.
nie chodzi o sortowanie tylko zapamiętanie w zmiennych i wyplucie na ekran.
Dopiero zaczynam przygodę z programowaniem i algorytmami.
Dzięki za wskazówki.