algorithm - 日常编码问题，1.4 : Running time given in the solution incorrect?

Question

---

序言:

我正在研究一本名为 Daily Coding Problem 的书中的一个特定难题。这是第一章的第四题。

问题陈述是:

Given an array of integers, return a new array where each element 
in the new array list is the number of smaller elements to the 
right of that element in the original input array.

他们提出了天真的解决方案，即遍历数组中每个元素的右侧元素并适当计数。这当然是 O(n^2) 时间。

然而，他们声称有一个解决方案可以在 O(nlogn) 时间内运行。所以几天来我一直在摸不着头脑。最后，出于不耐烦和挫败感，提出了几个不同的解决方案，但都没有改进 O(n^2)，我查看了他们的解决方案。

---

我的问题:

他们的解决方案正是我想出的解决方案之一。但是，当我考虑这个解决方案的运行时间时，我发现它是 O(n^2) 时间而不是 O(long) 时间，正如他们声称的那样。

我想要你的意见:)

算法:

1. 向后遍历输入列表
2. 维护一个已排序的元素列表
3. 查看当前元素，看看它适合在我们从后向前进行时正在构建的排序数组中的什么位置。

“分析:”

对于 n 元素数组中的每个元素，

1. 算法搜索正在构建的排序数组，找不到该元素的位置，O(logn)
2. 将该元素插入到数组中，O(n)(可能必须移动正在构建的整个排序数组)。

因此，对于 n 元素数组中的每个元素，搜索该元素的适当位置并将该元素插入正在构建的排序数组中的操作将是 O(logn + n) = O(n)，并且，因此，整个算法将是 O(n * n)。

例如，如果给定数组

 1 2 3 4 5 6 7 8 9 10

将每个元素插入到我们正在维护(构建)的排序数组中需要进行一次移位。

我错了吗？

感谢您的宝贵时间和反馈:)

Answer 1

你是对的，但如果你使用二叉堆进行插入就不是这样了。本质上是在做一种堆排序。

https://en.wikipedia.org/wiki/Binary_heap

插入操作在最坏的情况下是 O(logn)，之后您最后插入的元素成为子树的根，该子树具有子树中所有元素都小于根的属性。

二叉堆通常用于实现优先级队列。

更直接的解决方案是使用间接索引对数组进行排序。索引将为您提供当前元素右侧较小的元素数，因为这些元素使当前元素在未排序的数组中不在正确计数位置的位置。

#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int arr[6] = {8, 1, 3, 10, 5, 6};
//int arr[6] = {1, 2, 3, 4, 5, 6};
vector<int> a(begin(arr), end(arr));
 // sort using a custom function object
struct {
    bool operator()(int idx1, int idx2) const
    {   
        return a[idx1] < a[idx2];
    }   
} custom_compare;

int main(int argc, char** argv) {
    vector<int> idx(a.size(), 0);
    vector<int> result(a.size(), 0);
    for (int i = 0; i < a.size(); i++) {
        idx[i] = i;
    }
    sort(idx.begin(), idx.end(), custom_compare);
    for (int i = a.size() - 1; i >= 0; i--) {
        result[idx[i]] = i - idx[i];
        result[idx[i]] = result[idx[i]] < 0 ? 0 : result[idx[i]];
    }

    for (int i = 0; i < a.size(); i++) {
        cout << result[i] << " ";
    }
    cout << endl;
    return 0;
}

对于简单的示例，idx 如下所示:

1 2 4 5 0 3

所以元素 a[1] = 1 应该在位置 0，元素 a[2] = 3 应该在位置 1 等等。如果我们查看元素 0，它在排序数组中的位置 4 和未排序数组中的位置 0，那么有四个元素小于 8，保持 8, 4 个位置与其在排序数组中的位置相距。当然，对于位置不正确的数字，我们会得到负数，但因为更大的数字在前面，但我们只是将它们设置为 0。

程序运行后的结果如下所示:

4 0 0 2 0 0

所以8右边有4个比他小的元素，10有2个。