寻找满足特定条件

以下是我正在试图解决的问题的集合的元素的所有组合：我给定一组具有斜率m和常数c线。现在我需要找到在y轴右侧相交的这些线的交点数。这实质上意味着，对于线路1和2寻找满足特定条件

    c1>c2 and m2>m1

我需要计数的交点上Y轴的右侧的总数（如果算法存在）一个O（nlogn）算法。我总是可以用蛮力来获得o（n2）算法，但我正在寻找更快的算法。

来源

2013-05-11 Malice

您的意思是哪个路口？在第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

两个已排序的向量将做到这一点。

推所有的线到矢量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; 
}

这就是全部。如果您有任何问题，请给我留言。

来源

2013-05-11 08:31:24 Sayakiss

你能否详细说明步骤3？第4步应该为每个属于v1的c做对吗？ – Malice 2013-05-11 08:51:00

如何插入v1 logn？它应该是至少O（n）如果我没有错（你必须访问n个元素来插入它们） – Malice 2013-05-11 08:53:01

@Malice将它插入到v2。在STL :: SET中插入一个元素是log n。而STL :: Set可以被视为一个排序的向量。 – Sayakiss 2013-05-11 08:55:34

-1

在最坏的情况下，这个问题保证需要O（n^2）操作。

猜我画一条线，那么就不可能有交点。我可以在一个独特的点绘制一条与该线相交的线。现在我可以画一条与前面两条线相交的线。我可以继续绘制与前一行相交的线条。

这意味着的交叉点的数目可达到：

1 + 2 + 3 + 4 + 5 + ... + n-1个

鉴于大小n行的输入时，尺寸的这个问题的输出可能是（N *（N-1））/ 2个点或大约N的平方大于2.

因此，即使只是输出正确的答案，在最坏的情况下也需要O（n^2）。

编辑，忽略之前，我以为你想要的实际交点，而不仅仅是计数。

来源

2013-05-11 08:43:37 Xantix

我们只关心交点的数量。输出是一个数字。 – 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.两条线上得到相同的斜率，则让常数成为决定因素。

来源

2013-05-11 08:54:08 p1100i

寻找满足特定条件

回答

相关问题