"Usuwanie" powtarzajacych sie elementow tablicy

0

Czesc.
Mam tablice N punktow postaci (x,y).

Nie bardzo wiem jak najlepiej usunac z niej punkty powtarzajace sie (albo do drugiej tablicy przekopiowac unikaty).

Moge operowac tylko na tablicach i bez uzywania gotowych funkcji(typu unique w c++)

0

A jest ograniczony zakres na te współrzędne x,y? Bo jeśli jest wystarczająco mały to mozesz machnąć własną tablicę hashującą i usuwać w O(n). Jeśli zakres jest zbyt duży to możesz napisać drzewo i usunąć duplikaty w O(nlogn).
Możesz też posortować te punkty a potem usuwać duplikaty (bo będą zaraz obok siebie) też w O(nlogn).

0

Możesz też posortować te punkty a potem usuwać duplikaty (bo będą zaraz obok siebie) też w O(nlogn).

Myślałem nad tym, to trzeba by najpierw posortowac np. wzgledem x, a pozniej podzbiory o takich samych x wzgledem y?

A jest ograniczony zakres na te współrzędne x,y? Bo jeśli jest wystarczająco mały to mozesz machnąć własną tablicę hashującą i usuwać w O(n)

Mógłbyś przybliżyć jak miała by wyglądac idea takiego algorytmu?

0

Myślałem nad tym, to trzeba by najpierw posortowac np. wzgledem x, a pozniej podzbiory o takich samych x wzgledem y?

A to niby czemu? o_O Przecież nie ma dla ciebie znaczenia ich kolejność. Sortujesz struktury więc sortuj je od razu używając obu współrzędnych. Nie rozumiem twojego problemu. Sortowanie o którym mówisz miało by sens gdyby ważne było czy w tablicy posortowanej (1,1) ma być przed czy po (1,2), a to zupełnie nieistotne.

Mógłbyś przybliżyć jak miała by wyglądac idea takiego algorytmu?

Mogę, mimo że nie odpowiedziałeś na moje pytanie.
Załóżmy że dane są z zakresu 1-1000. Załóżmy trywialną funkcję hashującą f(x,y) = x+1000*y, jak nie trudno zauważyć taka funkcja daje nam unikalne przyporządkowanie parze (x,y) jednej liczby.
z ograniczeń wynika że maksymalna wartość f to 1000+10001000 = 10001000
Robimy więc sobie tablicę booleanów o takim rozmiarze, co kosztuje nas ~1MB pamięci.
Następnie przebiegamy wszystkie nasze punkty i robimy zwyczajnie tablica[f(x,y)] = true.
Następnie przebiegamy naszą tablicę i zapisujemy sobie tylko takie (x,y) dla których mamy true.
Złożoność takiego algorytmu to O(n) + O(k) gdzie k u nas wynosi `1000
zakres. Więc jeśli zakres jest duży a punktów jest mało to jest to mało opłacalne rozwiązanie, ale jeśli zakres jest mały a punktów dużo to algorytm zbiega toO(n)`
Oczywiście można też wymyślić inną funkcję hashującą, ale nie pokusiłeś się o podanie żadnych szczegółów, więc tego zrobić nie mogę.

0
Shalom napisał(a):

Myślałem nad tym, to trzeba by najpierw posortowac np. wzgledem x, a pozniej podzbiory o takich samych x wzgledem y?

A to niby czemu? o_O Przecież nie ma dla ciebie znaczenia ich kolejność. Sortujesz struktury więc sortuj je od razu używając obu współrzędnych. Nie rozumiem twojego problemu. Sortowanie o którym mówisz miało by sens gdyby ważne było czy w tablicy posortowanej (1,1) ma być przed czy po (1,2), a to zupełnie nieistotne.

To pewnie głupie pytanie ale jak mam posortowac używając od razu dwóch współrzędnych?

0

Takie coś powinno załatwić sprawę:

bool Point::operator<(const Point& second) const{
    if this.x < second.x{
        return true;
    }else if(this.x == second.x){
        return this.y < second.y;
    }
    return false;
}
0

Probowalem to zaimplementowac w quicksorcie ale mam StackOverflowException, nie wiem czemu.
Bazowalem na dzialajacym quicksorcie i jedynie przy podziale zmienilem while na cos takiego


bool Op(Point first,Point second)
{
        if (first.x < second.x)
        {
            return true;
        }
        else if (first.x == second.x)
        {
           return (first.y < second.y);
        }
        return false;
}

//tutaj while z podzialu

while(Op(T[right],pivot))
            right--;
while(!Op(T[left],pivot))
            left++;
0
  1. A czym są współrzędne x,y? Bo jak to są double to nie bardzo wolno ci porównywać znakiem równości..
  2. Co to za język? Bo wygląda na javę a w takim razie NIE WOLNO ci porównywać za pomocą == bo to porównuje REFERENCJE a nie WARTOŚCI (przy założeniu że ten x i y w Point to są Integer/Double).
  3. Na początek testuj ten komparator z bibliotecznym sortowaniem żeby wiedzieć czy błąd jest w twoim komparatorze czy w samym sortowaniu...
0

Zmienne sa normalnie int, to bylo pisane w C#, ale sprawdzilem w C i tez nie dziala.

Chyba jednak z komparerem jest cos nie tak bo ten kod na zwyklych intach i bez tego komparera dziala a po przerobce na to:

struct Point
    {
        public int x,y;
    }
class Program
    {
    static bool Test(Point p1,Point x)
        {
            if (p1.x < x.x)
                return true;
            else if (p1.x == x.x)
                if (p1.y < x.y)
                    return true;
                else
                    return false;
            return false;
        }
    static int partitionQuick(int l,int p, Point[] T)
    {
        Point x = T[l];
        int i=l,j=p;
        while(true)
        {
            while(Test(T[j],x))
                j--;
            while(!Test(T[i],x))
                i++;
            if(i<j)
            {
                Point temp = T[i];
                T[i] = T[j];
                T[j] = temp;
                i++;j--;
            }
            else
                return j;
        }
    }
    static void quickSort(int l, int p,Point[] T)
    {
        int q;
        if(l<p)
        {
            piv = partition(l,p, T);
            quickSort(l,piv, T);
            quickSort(piv+1,p, T);
        }
    }
}

Albo stackoverflow, albo przy while wychodzi poza indeks tablicy.

0
            while(!Test(T[i],x))
                i++;

Ty tak poważnie? Rozumiesz że ten komparator zwraca porządek którego nie wolno ci tak użyć? Spałeś na algebrze? Wiesz czym różni się porządek silny i słaby? Pomyśl co komparator zwróci dla dwóch identycznych elementów... Zwróci ci "false" bo nie jest prawdą że x<x ani że y<y, więc iteracja poleci dalej. A jeśli akurat elementem z którym porównywałeś był koniec tablicy to cóż... ;]
Dlatego prosiłem żebyś testował na porządnej implementacji sortowania...
Patrz:
http://ideone.com/xpzXc6

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