Mam dane n punktow plaszczyzny (x,y), z punktow o takich samych wspolrzednych x mam zostawic te o najwiekszych y.
Najpierw posortowałbym punkty wzgledem wspolrzednych x.
Ale jak teraz najprosciej/najmniej kosztownie zostawic te ktore maja najwieksza wspolrzedna y? Moglbym teraz z kolei posortowac wzgledem y podzbiory punktow o takich samych x, ale nie wiem czy jest to dobry pomysl.
Moze da sie prosciej wybrac te o najwiekszej wspol. y z punktow o takiej samej wspol. x ?
Sortowanie wydaje mi sie zupełnie bez sensu. Nie mozesz po prostu iterować po wszystkich punktach i sobie powybierać? Dostaniesz rozwiązanie w O(n) a nie O(nlogn)
point = collections.namedtuple('point', ['x', 'y'])
punkty = [point(random.randint(0,10), random.randint(0,10)) for i in range(100)]
max_points = {}
for punkt in punkty:
if punkt.x not in max_points:
max_points[punkt.x] = punkt.y
else:
max_points[punkt.x] = punkt.y if punkt.y > max_points[punkt.x] else max_points[punkt.x]
Ciekawe rozwiazanie, ale piszac w czystym C troche ten kod by sie rozrosl.
To zależy od tego ile różnych Xów masz na dobrą sprawę. Jeśli na tyle mało ze da się zrobić zwykłą tablicę gdzie indeksem będzie współrzędna X / wartość pewnej funkcji obliczonej dla współrzędnej X to kod będzie równie krótki.