如何将统计A[j]>B[i]的双层嵌套循环O(N*N)复杂度优化至O(N)？

首先明确：不可能将该问题的时间复杂度优化到O(N)。因为这类需要跨数组比较元素大小关系的计数问题，基于比较的算法时间复杂度下界是O(N log N)——除非你的数组元素有特殊约束（比如取值范围极小，可以用线性时间的计数排序），否则无法突破这个下界。

排序确实是有效的优化手段 #

排序能帮你把时间复杂度从O(N²)降到O(N log N)，这是当前问题的最优解。你的需求是统计所有满足i < j且A[j] > B[i]的数对数量，核心思路是对每个j，快速找出0 ≤ i < j中B[i] < A[j]的元素个数，再将这些个数累加。

具体实现示例（以C++为例）

我们可以通过维护动态有序的B数组前缀，结合二分查找来高效统计：

#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

int countValidPairs(vector<int>& A, vector<int>& B) {
    int n = A.size();
    int result = 0;
    vector<int> sortedBPrefix;

    for (int j = 0; j < n; ++j) {
        // 当j>=1时，将B[j-1]插入有序前缀数组（保证前缀是B[0..j-1]的有序状态）
        if (j > 0) {
            auto insertPos = lower_bound(sortedBPrefix.begin(), sortedBPrefix.end(), B[j-1]);
            sortedBPrefix.insert(insertPos, B[j-1]);
        }
        // 统计前缀中小于A[j]的元素数量
        if (!sortedBPrefix.empty()) {
            auto countPos = lower_bound(sortedBPrefix.begin(), sortedBPrefix.end(), A[j]);
            result += countPos - sortedBPrefix.begin();
        }
    }
    return result;
}

int main() {
    vector<int> A = {3,1,4,2};
    vector<int> B = {2,4,1,3};
    cout << countValidPairs(A, B) << endl;
    return 0;
}

这个实现中，sortedBPrefix始终维护B[0..j-1]的有序状态，每次插入和统计都用二分查找（O(log j)时间），总时间复杂度为O(N log N)，比原O(N²)的嵌套循环高效得多。

为什么O(N)做不到？ #

要统计A[j] > B[i]的数对，必须明确两个数组元素的相对大小分布。而基于比较的排序算法无法在O(N)时间完成——这是计算机科学的经典结论：基于比较的排序下界是Ω(N log N)。只有当数组元素有特殊属性（比如取值范围固定且极小）时，才能用计数排序等线性时间算法辅助，但通用场景下无法达到O(N)复杂度。

内容的提问来源于stack exchange，提问作者mr. noone