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;
}

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