计算满足给定条件的三元组

Question

给定一个大小为 N 的数组 A 我需要计算这样的三元组 (i,j,k) 这样：

Condition 1 : i < j < k
Condition 2 : A[i] > A[j] > A[k]

我知道 O(N^3) 解决方案。他们可以像 O(N) 或 O(NlogN) 解决这个问题吗，因为 N 可以高达 100000

示例： 让 N=4 和数组为 [4,3,2,1] 那么答案是 4 作为 {4,3,2},{4,3,1},{4,2,1} 和 {3,2,1} 都是可能的答案

如何找到给定 N 和数组 A 的计数？

我的方法：

int n;
cin>>n;
vector<int> A(n);
for(int i=0;i<n;i++){
    cin>>A[i];
}
int count=0;
for(int i=0;i<n;i++){
    for(int j=i+1;j<n;j++){
        for(int k=j+1;k<n;k++){
            if(A[i]>A[j] && A[j]>A[k]){
                count++;
            }
        }
    }
}
cout<<count<<"\n";

Answer 1

你可以在 O(n*n) 中很容易地做到这一点，你只需要跟踪每个元素有多少个较小的数字：

vector<int> smallerNumbers(A.size());

for (int i = A.size() - 2; i >= 0; --i){
    for (int j = i + 1; j < A.size(); ++j){
        if (A[i] > A[j]){
            smallerNumbers[i]++;
            count += smallerNumbers[j];
        }
    }
}

对于 O(nklogn) 解决方案，请在此处查看我的答案：

请注意，这是递增序列，而您要求的是递减序列。

为此，您需要反转 mapIndex 创建的排名。因此，只需将 temp 与 partial_sort_copy 行交换，即可在创建 mapIndex 之前反转：

   partial_sort_copy(values.cbegin(), values.cend(), temp.rbegin(), temp.rend());

Answer 2

首先对数组进行排序，维护每个元素的索引。

class Node{
    int index, val;
}

要比较两个节点，我们首先需要比较它们的值。如果值相等，我们将比较它们的索引，如果一个节点的索引较小.

，则认为该节点更大

现在，按排序顺序处理每个节点，我们尝试将每个节点的索引添加到Fenwick tree。因此，对于每个索引 i，我们在树中查询该索引的频率，该索引先前已添加到树中。这是值大于当前索引值的索引数。

注意对于case元素相等的情况，通过上面提到的排序机制，我们会先把index大的加入到树中，这样不影响从树中查询频率值。

应用类似的步骤来获取那些小于 i 且索引为 j < i.

的元素

例如：

如果我们有一个数组

{0(1) ,1(2) , 2(2) ,3(4) , 4(4) ,5(4) ,6(1)} //index(value)

After sort -> {5(4), 4(4), 3(4), 2(2), 1(2), 6(1), 0(1) }

伪代码

Node[]data;

sort(data)
Fenwick tree;
int[]less;
int[]more;
for(int i = 0; i < data.length; i++){
    less[data[i].index] = tree.query(data[i].index);
    tree.add(data[i].index, 1);
}

tree.clear();
for(int i = data.length - 1; i >= 0; i--){
    more[data[i].index] = tree.query(data.length) -tree.query(data[i].index);
    tree.add(data[i].index, 1);
}
int result = 0;
for(int i = 0; i < data.length; i++)
    result += more[i]*less[i];

时间复杂度为 O(n logn)。

工作 Java 代码（FT 是我的 Fenwick 树）

    PrintWriter out;
    Scanner in = new Scanner(System.in);

    out = new PrintWriter(System.out);
    int n = in.nextInt();
    Node[] data = new Node[n];
    for (int i = 0; i < n; i++) {
        data[i] = new Node(i + 1, in.nextInt());
    }
    FT tree = new FT(n + 2);
    Arrays.sort(data, new Comparator<Node>() {
        @Override
        public int compare(Node o1, Node o2) {
            if (o1.val != o2.val) {
                return o2.val - o1.val;
            }
            return o2.index - o1.index;
        }
    });

    int[] less = new int[n];//Store all nodes with greater index and smaller value;
    int[] greater = new int[n];//Store all nodes with smaller index and greater value
    for (int i = 0; i < n; i++) {
        greater[data[i].index - 1] = (int) tree.get(data[i].index);
        tree.update(data[i].index, 1);
    }
    tree = new FT(n + 2);
    for (int i = n - 1; i >= 0; i--) {
        less[data[i].index - 1] = (int) (tree.get(n) - tree.get(data[i].index));
        tree.update(data[i].index, 1);
    }


    long total = 0;
    for (int i = 0; i < n; i++) {
        total += less[i] * greater[i];
    }
    out.println(total);
    out.close();

计算满足给定条件的三元组

Count triplets which satisfy given condition

c++

algorithm

dynamic-programming