Struktura danych do filtrowania wszystkich par-więcej punktów?

Question

Co to jest dobre wdrożenie następujących elementów?

Struktura danych nie może zawierać żadnego punktu, który jest większy od drugiego. na przykład (2,11)> (1,10), (5, 5) nie-gt (1,5). Dane wejściowe pojawiają się w Internecie, więc nie można ich wstępnie zamówić/przygotować.

porządku, może być przedstawiony w powyższym obrazu. Tak więc, każdy punkt jest umieszczony w podanej kolejności, a mianowicie:

1. (2,2) umieszczonej
2. (2,4) włożona,> (2,2), i vice versa, tak jak pozostają
3. (3,3)> (2,2) i dlatego nie wstawiono
4. (1,1); wszystkie inne> tak (1,1) wstawione, a wszystkie inne usunięte

Pomysły?

Answer 1

Pojedynczo połączona lista z punktami, które są parami mniej niż inne.

Należy rozważyć sytuację porównania nowy punkt dla każdego punktu na liście na bieżącym etapie. Сheck: nasz punkt mniej niż punkt kontrolny na liście?

Jeśli tak, usuń z punktu sprawdzania listy.

W przeciwnym razie po prostu dodaj nowy punkt do listy.

Na końcu lista zawiera takie punkty.

Answer 2

start z tablicy punktów (inf, inf) i (Inf, -Inf)

Zamówienie elementy w tablicy poniżej w odniesieniu do reguły

for (x,y) and (t,z) 
if x<t (x,t) is before (t,z) 
if x=t and y>z then (x,t) is before (t,z) 

gdy chcesz wstawić element, znajdź element o najwyższym porządku, który jest przed wstawionym elementem i nazwij go EBefore. Znajdź również element o najniższym porządku, który jest po wstawionym elemencie i nazwij go EAfter. Możesz użyć wyszukiwania binarnego podczas znajdowania tych dwóch elementów.

Jeśli Vectoral produktem

EInserted x (EAfter - EBefore) > 0 

usunąć wszystkie elemets między EBefore i EPo i wstawić EInserted między nimi. Jeśli produkt jest negatywny, nie dodawaj elementu.