java - 如何查找某个数组元素左侧有多少个元素大于该元素？

Question

给定一个数组，我想找出哪个元素 x 左侧有最多大于 x 的数字。例如，在数组 [3, 3, 1, 8, 2, 9] 中，元素 2 的左侧有 3 个数字大于其自身。

这个问题的答案应该是值左边较大数字的数量。这是我明显的强力解决方案:

    int biggest = 0;
    for (int i = 0; i < n; i++) {
        int num = 0;
        for (int j = 0; j < i; j++)
            if (a[j] > a[i])
                num++;
        biggest = Math.max(biggest, num);
    }

但是，这会在 O(n^2) 时间内运行，这是不希望的。我怎样才能更快地解决这个任务？

Answer 1

如果 TreeSet 的 tailSet 有一个有效的 size 实现，这样的事情就会起作用。但据我所知，它是 O(n) 而不是 O(log(n)) 。

int biggest = 0;
TreeSet<Integer> set = new TreeSet<>();
for (int x : a) {
    int num = set.tailSet(x).size();
    biggest = Math.max(biggest, num);
    set.add(x);
}

所以这只是想法。如果您实现自己的TreeSet，那么它就会起作用，其中每个节点都会记住其右子节点的大小。插入仍然是 O(log(n))，大小计算也将是 O(log(n))，整个循环则 O( n * log(n))。

这肯定是可行的，只是需要做一些工作。