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
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+1000*1000 = 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 to O(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
- A czym są współrzędne x,y? Bo jak to są double to nie bardzo wolno ci porównywać znakiem równości..
- 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).
- 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
0
To by wiele wyjaśniało :)
Dzięki za pomoc.
A co do algebry to nie spałem na niej bo jeszcze jej nie miałem :P