r**m
发帖数: 1825 | 1 给定一组（二维）坐标点的集合，对于一给定输入点，实现空间和时间都是最优的的算
法确定此坐标点是否在集合中？
（x0, y0),(x1,y1)....(xn,yn)
Implement
bool IsInSet(Xin, Yin)
这个坐标系的0
不需要用到Geometric hashing |
l*********8
发帖数: 4642 | 2 quad-tree?
【在 r**m 的大作中提到】
: 给定一组（二维）坐标点的集合，对于一给定输入点，实现空间和时间都是最优的的算
: 法确定此坐标点是否在集合中？
: （x0, y0),(x1,y1)....(xn,yn)
: Implement
: bool IsInSet(Xin, Yin)
: 这个坐标系的0: 不需要用到Geometric hashing
|
E*******0
发帖数: 465 | 3 1.先用xin去比较所有点的x坐标，把相等的标记；
2.用yin去比较所有的y坐标，把相等的标记。
3.用1000个bit位去标记。
4.把1和2得到两个标记数值求&&.
5.把有标记位的相应的点的坐标输出。 |
t****t
发帖数: 6806 | 4 你这个方法甚至还不如无脑挨个比较.
【在 E*******0 的大作中提到】
: 1.先用xin去比较所有点的x坐标，把相等的标记；
: 2.用yin去比较所有的y坐标，把相等的标记。
: 3.用1000个bit位去标记。
: 4.把1和2得到两个标记数值求&&.
: 5.把有标记位的相应的点的坐标输出。
|
E*******0
发帖数: 465 | 5 int XY[][]; //coordinate points.
int numXY; //length of points in the set
bool IsInSet(Xin, Yin)
{
long Xlabel, Ylabel;//assume 64 bits long type.
//First, we segment the points set into several 64-bit sets and one
sit with smaller than 64 bits.
int iteNum = numXY / 64; // number of sets with 64 bits.
int remianNum = numXY % 64; // number of set with smaller 64 bits
//output the points in the set with smaller 64 bits.
Xlabel=0;
Ylabel=0
for (int j=1； j<=remainNum; j++)
{
if (Xin==XY(j,1))
Xlabel=Xlabel+2^(j-1);
if (Yin==XY(j,2))
Ylabel=Ylabel+2^(j-1);
}
Xlabel=Xlabel&&Ylabel;
for (j=1; j
{
if (Xlabel % 2!=0)
output (XY(j,1), XY(j,2));
Xlabel=Xlable/2;
}
//output the points in the sets with 64 bits.
for (int i=1; i<=iteNum; i++)
{
Xlabel=0;
Ylabel=0
for (int j=1； j<=64; j++)
{
if (Xin==XY(i*64+j,1))
Xlabel=Xlabel+2^(j-1);
if (Yin==XY(i*64+j,2))
Ylabel=Ylabel+2^(j-1);
}
Xlabel=Xlabel&&Ylabel;
for (j=1; j<64; j++)
{
if (Xlabel % 2!=0)
output (XY(i*64+j,1), XY(i*64+j,2));
Xlabel=Xlable/2;
}
}
} |
E*******0
发帖数: 465 | |
E*******0
发帖数: 465 | 7
你难道能够想到更好的方法么？
【在 t****t 的大作中提到】
: 你这个方法甚至还不如无脑挨个比较.
|
y****n
发帖数: 743 | 8 因为给定的坐标集合没有任何规律（顺序）,无论怎样优化，每个做标都需要处理一下。
所以最优的时间复杂度应该是O(n)。
所以，最简单的循环比较应该是空间和时间都是最优的的算法。
【在 r**m 的大作中提到】
: 给定一组（二维）坐标点的集合，对于一给定输入点，实现空间和时间都是最优的的算
: 法确定此坐标点是否在集合中？
: （x0, y0),(x1,y1)....(xn,yn)
: Implement
: bool IsInSet(Xin, Yin)
: 这个坐标系的0: 不需要用到Geometric hashing
|
E*******0
发帖数: 465 | 9 我考虑到如果用int变量来标记的话，空间复杂度会是O(n)，如果用bit来标记，复杂度
会降低。
而且，我是64个点64个点的处理的。所以，空间复杂度是O(1). |
p*****2
发帖数: 21240 | |
|
|
t****t
发帖数: 6806 | 11 我不是说了么, 无脑比较就比你这个强啊! 复杂度一样, 程序长度是你的1/10, 还易读!
bool is_in_set(int x, int y)
{
for (int i=0; i
if (x==data[i].x && y==data[i].y) return true;
}
return false;
}
当然我不是说无脑比较就是最好. 但是要是做得比无脑比较还要差, 那你还拿出来干嘛?
【在 E*******0 的大作中提到】
: 我考虑到如果用int变量来标记的话，空间复杂度会是O(n)，如果用bit来标记，复杂度
: 会降低。
: 而且，我是64个点64个点的处理的。所以，空间复杂度是O(1).
|
t****t
发帖数: 6806 | 12 这算法已经够差的了, 这实现的比算法还要差!
【在 E*******0 的大作中提到】
: int XY[][]; //coordinate points.
: int numXY; //length of points in the set
: bool IsInSet(Xin, Yin)
: {
: long Xlabel, Ylabel;//assume 64 bits long type.
:
: //First, we segment the points set into several 64-bit sets and one
: sit with smaller than 64 bits.
: int iteNum = numXY / 64; // number of sets with 64 bits.
: int remianNum = numXY % 64; // number of set with smaller 64 bits
|
t****t
发帖数: 6806 | 13 先问清楚能不能对数据预处理吧...
【在 l*********8 的大作中提到】
: quad-tree?
|
E*******0
发帖数: 465 | |
t****t
发帖数: 6806 | 15 why do you want to mark in the first place? it's totally unnecessary and
waste of time.
【在 E*******0 的大作中提到】
: 我考虑到如果用int变量来标记的话，空间复杂度会是O(n)，如果用bit来标记，复杂度
: 会降低。
: 而且，我是64个点64个点的处理的。所以，空间复杂度是O(1).
|
y****n
发帖数: 743 | 16 我觉得thrust在楼上给的无脑比较是最佳算法。
不需要额外空间，算法O(n)。
【在 E*******0 的大作中提到】
: 要不你给个好的算法，看看阿。
|
t****t
发帖数: 6806 | 17 如果不能预处理, 这个就可以了. 但是考虑到面试题一般不会这么简单, 还是问清楚比
较好.
【在 y****n 的大作中提到】
: 我觉得thrust在楼上给的无脑比较是最佳算法。
: 不需要额外空间，算法O(n)。
|
y****n
发帖数: 743 | 18 只是就题论题，如果能预处理还要平衡“时间和空间”和“空间换时间”的问题。
因为原题要求时间空间都优化。
【在 t****t 的大作中提到】
: 如果不能预处理, 这个就可以了. 但是考虑到面试题一般不会这么简单, 还是问清楚比
: 较好.
|
r**m
发帖数: 1825 | 19 Nod, 应该先问一下这个，已知的点集合是否可以预处理。
用简单hash是不是最快。
【在 p*****2 的大作中提到】
: 如果要是多次调用的话到可以优化一下。
|
H****r
发帖数: 2801 | 20 x0-xn, y0-yn 是啥类型？
【在 r**m 的大作中提到】
: 给定一组（二维）坐标点的集合，对于一给定输入点，实现空间和时间都是最优的的算
: 法确定此坐标点是否在集合中？
: （x0, y0),(x1,y1)....(xn,yn)
: Implement
: bool IsInSet(Xin, Yin)
: 这个坐标系的0: 不需要用到Geometric hashing
|
|
|
r**m
发帖数: 1825 | 21 integer
【在 H****r 的大作中提到】
: x0-xn, y0-yn 是啥类型？
|
H****r
发帖数: 2801 | 22 if 0
to generate some ID for O(1) search. For example :
a = min(x,y)
b = max(x,y)
id = a + b*1000
【在 r**m 的大作中提到】
: integer
|
g**x
发帖数: 373 | 23 why not
id = x*1000 + y?
I guess the next question interviewer will ask is, what to do if the
coordinates are distributed randomly and widely.
If not using hash, sorting seems to be necessary. So it has to be O(NlogN)?
【在 H****r 的大作中提到】
: if 0: to generate some ID for O(1) search. For example :
: a = min(x,y)
: b = max(x,y)
: id = a + b*1000
|
H****r
发帖数: 2801 | 24 my bad. id = x*100 + y is good. min,max are wrong lolz
【在 g**x 的大作中提到】
: why not
: id = x*1000 + y?
: I guess the next question interviewer will ask is, what to do if the
: coordinates are distributed randomly and widely.
: If not using hash, sorting seems to be necessary. So it has to be O(NlogN)?
|
m*****y
发帖数: 93 | 25 用preprocessing.
kd-tree: O(n) space, O(sqrt(n)) query time.
range-tree w/ factorial cascading: O(nlogn) space, O(logn) query time. |
y*******g
发帖数: 6599 | 26 kd tree面试的时候基本写不出吧。。
【在 m*****y 的大作中提到】
: 用preprocessing.
: kd-tree: O(n) space, O(sqrt(n)) query time.
: range-tree w/ factorial cascading: O(nlogn) space, O(logn) query time.
|
e***l
发帖数: 710 | 27 实际应用肯定hash，几行code就完了，而且O(1)时间查找。
不hash的话，直接radix sort这些点，就是先对x排序，再对y排序，O(NlogN)。
以后每次查找只需要O(logN)，二分查x，然后在x相同的点中查y。 |
