optimization - 如何将执行时间从 O(N^2) 变为 O(N)

Question

我试图在线解决一个编程问题(既不是我的家庭作业也不是我的任何面试/测试，但可以成为一个很好的候选人)。问题如下。我下面的代码在功能上是正确的，但它的运行时复杂度为 O(N²)，而预期的解决方案应该在 O(N) 中。

我尝试了其他几种方法来优化它 - 1) 对数组进行排序，然后尝试是否可以使它正常工作，但是由于排序会导致原始数字的索引丢失，我什至将它们保存在一个单独的数组中，并解决了它，但即使这样最终也是 O(N²)。我确信对数组进行排序将有助于达到 O(N)，但无法确定它。

使用任何方法在 O(N) 内完成此问题的任何帮助都是有用的。

(抱歉发帖太长)

考虑一个由 N 个整数组成的零索引数组 A。该数组的索引是从 0 到 N-1 的整数。取一个索引 K。如果 A[J] > A[K]，则索引 J 被称为 K 的上升沿。请注意，如果 A[K] 是数组 A 中的最大值，则 K 没有升序。

如果 abs(K−J) 是最小的可能值(即，如果 J 和 K 之间的距离最小)，则 K 的上升沿 J 被称为 K 的最近上升沿。请注意，K 最多可以有两个最接近的上升点:一个比 K 小，一个比 K 大。

例如，让我们考虑以下数组 A:

A[0] = 4 A[1] = 3 A[2] = 1 A[3] = 4 A[4] = -1 A[5] = 2 A[6] = 1 A[7] = 5 A[8] = 7

如果 K = 3，则 K 有两个上升点:7 和 8。它最近的上升点是 7，K 和 7 之间的距离等于 abs(K−7) = 4。

写一个函数:

struct Results {
  int * R;
  int N;
};

struct Results array_closest_ascenders(int A[], int N);

给定一个包含 N 个整数的零索引数组 A，返回一个包含 N 个整数的零索引数组 R，这样(对于 K = 0,..., N−1):

    if K has the closest ascender J, then R[K] = abs(K−J); that is, R[K] is equal to the distance between J and K,
    if K has no ascenders then R[K] = 0.

例如，给定以下数组 A:

A[0] = 4 A[1] = 3 A[2] = 1 A[3] = 4 A[4] = -1 A[5] = 2 A[6] = 1 A[7] = 5 A[8] = 7

该函数应返回以下数组 R:

R[0] = 7 R[1] = 1 R[2] = 1 R[3] = 4 R[4] = 1 R[5] = 2 R[6] = 1 R[7] = 1 R[8] = 0

数组 R 应返回为:

    a structure Results (in C), or
    a vector of integers (in C++), or
    a record Results (in Pascal), or
    an array of integers (in any other programming language).

假设:

    N is an integer within the range [0..50,000];
    each element of array A is an integer within the range [−1,000,000,000..1,000,000,000].

复杂度:

    expected worst-case time complexity is O(N);
    expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).

可以修改输入数组的元素。

我的解决方案(O(N²)):

#include <math.h>
#include "stdio.h"
#include "stdlib.h"

struct Results
{
    int *R;
    int N;
};

struct Results array_closest_ascenders ( int A[], int N )
{
    struct Results result;


     int i,j,asc_found=0;

     result.R = (int*)malloc(sizeof(int)*N);

     for(i=0;i<N;i++)
       result.R[i] = N;

     result.N = N;

     for(i=0;i<N;i++)
     {
       asc_found = 0;
       for(j=0;j<N;j++)
       {
         if(A[i] < A[j])
         {
           //if(result.R[i] == 0)
           {
               if(result.R[i] > abs(i-j))
               {
                    result.R[i] = abs(i-j);
                    asc_found = 1;
               }
           }
         }
       }
       if(asc_found == 0)
           result.R[i] = 0;
     }


    return result;
}

void main()
{

    //int A[] = {4, 3, 1, 4, -1, 2, 1, 5, 7};
    int A[] = {691446939, -241956306, 485954938, 604054438, 383714185, -656099986, -357341170, -255988102, -139683363, -463281394, -382925609, 712727854};
    struct Results tmp;

    tmp = array_closest_ascenders(A,sizeof(A)/sizeof(A[0]));

}

Answer 1

Left closest ascender 和right closest ascender 可以分开考虑。我们遍历数组一次，计算左边最近的上升点；并再次在相反的方向上，计算右边最近的上升点。最近的上升器是两者中较近的一个。

在下面的算法中，只考虑了左上角。一堆索引跟踪当前元素的左上行(所有)。最近的上升器总是在堆栈的顶部。

for i in 0 .. N
  while (!stack.empty) && (A[stack.top] <= A[i])
    stack.pop
  if stack.empty
    then R[i] = 0
    else R[i] = i - stack.top
  stack.push(i)