寻找满足特定条件
以下是我正在试图解决的问题的集合的元素的所有组合: 我给定一组具有斜率m和常数c线。现在我需要找到在y轴右侧相交的这些线的交点数。这实质上意味着,对于线路1和2寻找满足特定条件
c1>c2 and m2>m1
我需要计数的交点上Y轴的右侧的总数(如果算法存在)一个O(nlogn)算法。我总是可以用蛮力来获得o(n2)算法,但我正在寻找更快的算法。
两个已排序的向量将做到这一点。
- 推所有的线到矢量V1。
- 按常数排序v1。之后,v1 [0]是最小c的行。
- Traversal v1从开始到结束。对于v1中的每个元素e,我们只应考虑之前访问的元素(c1> c2)。现在的任务是在所有被访问的元素中找到m2> m1的元素。
- 所以我们只是将已经访问过的元素推入向量v2中。每次插入后,我们应该按照斜率m对它进行排序(自我平衡BST将完成此任务)。由于v2是按m排序的,二叉搜索会告诉你有多少元素满足m2> m1。
排序为n日志ñ。
插入到v2是log n(它可以通过自平衡BST来实现,并且它会调用n次)。
二进制搜索日志N(调用n次)。
所以这是O(n日志n)的
如果你写在C++,它会像那个(我不定义V2,因为你要实现一个自平衡BST):
struct line
{
int c,m;
line(int a,int b):c(a),m(b){}
bool operator <(const line &a) const
{
return m>a.m;
}
};
bool cmp(const line &v1,const line &v2)
{
return v1.c<v2.c;
}
int main()
{
vector<line> v1;
v1.push_back(line(1,3));
v1.push_back(line(4,1));
v1.push_back(line(3,1));
v1.push_back(line(2,2));
sort(v1.begin(),v1.end(),cmp);
int ans=0;
for(int i=0;i<v1.size();i++)
{
int num=v2.find(v1[i]);//return the number of element whose m is larger than v1[i].
ans+=num;
v2.insert(v1[i]);// in every step, the element e in v2 will satisfy e.c<v1[i].c
}
cout << ans;
}
这就是全部。如果您有任何问题,请给我留言。
在最坏的情况下,这个问题保证需要O(n^2)操作。
猜我画一条线,那么就不可能有交点。我可以在一个独特的点绘制一条与该线相交的线。现在我可以画一条与前面两条线相交的线。我可以继续绘制与前一行相交的线条。
这意味着的交叉点的数目可达到:
1 + 2 + 3 + 4 + 5 + ... + n-1个
鉴于大小n行的输入时,尺寸的这个问题的输出可能是(N *(N-1))/ 2个点或大约N的平方大于2.
因此,即使只是输出正确的答案,在最坏的情况下也需要O(n^2)。
编辑,忽略之前,我以为你想要的实际交点,而不仅仅是计数。
我们只关心交点的数量。输出是一个数字。 – Sayakiss 2013-05-11 08:45:41
我张贴我的解决方案,因为我觉得它更容易实现:
比方说,你得到了线的对象,以下属性定义:
- m (slope, initialized on start)
- c (constant, initialized on start)
- pos_m (default 0 value)
- pos_c (default 0 value)
现在,你有一个V
这些线的向量,则:通过在元件使用键m
- 排序
V
(O(nlogn))。 - 迭代
V
,索引i
集合V[i].pos_m = i
(O(n))。 - 通过在元素(O(nlogn))上使用密钥
c
对V
进行排序。 - 迭代
V
,索引i
集合V[i].pos_c = i
。 (上))。 - 让
result = 0
现在V
指数迭代i
做result += | V[i].pos_m - V[i].pos_c |
(O(n))的
分拣,如果比较的值等于再使用其他主要的决定的顺序(如果两者相等,它们是同一条线)。例如,如果在1.两条线上得到相同的斜率,则让常数成为决定因素。
您的意思是哪个路口?在第1行和第2行之间?或者在线和X轴之间? – 2013-05-11 07:59:22
我需要找出给定集合中位于x = 0右侧的行之间的交点数。 – Malice 2013-05-11 08:24:09
如果您创建根据您的标准排序的行列表,会发生什么情况?然后,您可以遍历列表并总结列表条目的数量。复杂度O(n log(n)) – 2013-05-11 08:30:22