algorithm - 查找满足特定条件的集合中元素的所有组合

Question

这是我要解决的一个问题：给定一组具有斜率 m 和常数 c 的线。现在我需要找到在 y 轴右侧相交的这些线的交点数。这基本上意味着对于第 1 行和第 2 行

                    c1>c2 and m2>m1

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

Answer 1

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

1. 将所有线推入向量 v1。
2. 按常数 c 对 v1 进行排序。之后，v1[0] 是 c 最小的线。
3. 从头到尾遍历 v1。对于 v1 中的每个元素 e，我们应该只考虑之前访问过的元素（c1>c2）。现在的任务是在所有访问过的元素中找到 m2 > m1 的元素。
4. 因此，我们只需将已访问的元素推入向量 v2 中。我们应该在每次插入后按斜率 m 对其进行排序（自平衡 BST 将执行此任务）。由于 v2 按 m 排序，二分查找会告诉您有多少元素满足 m2>m1。

排序是 n log n。

插入v2是log n（可以用自平衡BST实现，会调用n次）。

二分查找是 log n（调用 n 次）。

所以它是 O(nlog 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;
}

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

Answer 2

我发布我的解决方案是因为我认为实现起来更简单：

假设您有 Line 的对象，并定义了以下属性：

- m (slope,    initialized on start)
- c (constant, initialized on start) 
- pos_m ( default 0 value )
- pos_c ( default 0 value )

现在，你有V这些线的向量，然后：

1. V通过使用m元素上的键 (O(nlogn)) 进行排序。
2. V在索引i集V[i].pos_m = i(O(n))上迭代。
3. V通过使用c元素上的键 (O(nlogn)) 进行排序。
4. 迭代V，在索引i集上V[i].pos_c = i。（在））。
5. 现在让我们result = 0迭代V索引ido result += | V[i].pos_m - V[i].pos_c |(O(n))

在排序时，如果比较值相等，则使用另一个键来决定顺序（如果两者相等，则它们是同一行）。例如，如果 1. 两条线的斜率相同，则让常数成为决定因素。

Answer 3

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

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

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

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

给定一个大小为 n 行的输入，这个问题的输出大小可能是 (N*(N-1))/2 点或大约 N 平方超过 2。

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

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