每日编码问题,1.4:解决方案中给出的运行时间不正确?

问题描述 投票:0回答:1

前言:

我正在编写一本名为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(长)时间,正如他们声称的那样。

我想你的意见:)

算法:

  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

将每个元素插入到我们维护(构造)的排序数组中需要移位。

我不对吗?

感谢您的时间和反馈:)

algorithm performance
1个回答
2
投票

你是对的,但如果使用二进制堆进行插入则不行。从根本上做了一种堆排序。

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个。

© www.soinside.com 2019 - 2024. All rights reserved.