如何查找数组中大于其后所有元素的元素数量？

Question

我有一个函数，它接受N个正整数的一维数组，并返回比下一个大的元素的数量。问题是存在一个功能来做到这一点，在一个更好的时间？我的代码如下：

int count(int *p, int n) { 
    int i, j; 
    int countNo = 0; 
    int flag = 0; 
    for(i = 0; i < n; i++) { 
     flag = 1; 
     for(j = i + 1; j < n; j++) { 
      if(p[i] <= p[j]) { 
       flag = 0; 
       break; 
      } 
     } 
     if(flag) { 
      countNo++; 
     } 
    } 
    return countNo; 
} 

我的解决办法是O(n^2)。它可以做得更好吗？

Answer 1

可以在O(n)完成。

int count(int *p, int n) { 
    int i, currentMax; 
    int countNo = 0; 
    currentMax = p[n-1]; 
    for(i = n-1; i >= 0; i--) { 

    if(currentMax < p[i]) 
    { 
     countNo ++; 
     currentMax = p[i]; 
    } 
    } 
    return countNo; 
} 

Answer 2

创建一个辅助阵列aux：

aux[i] = max{arr[i+1], ... ,arr[n-1] } 

它可以在线性时间内通过从右向左扫描该阵列来完成。

现在，你只需要这样arr[i] > aux[i]

这是在做O(n)元素的数量。

Answer 3

向后走向阵列，并跟踪当前最大值。每当你找到一个新的最大值时，该元素都大于后面的元素。

Answer 4

可以解决线性时间（O(n) time）这个问题。请注意，数组中的最后一个数字将始终是适合问题定义的有效数字。所以函数将始终输出一个大于等于1的值。

对于数组中的任何其他数字都是有效数字，它必须大于或等于该数字之后的最大数字阵列。

所以从右侧的阵列上遍历左跟踪发现到现在的最大数量，并增加计数器的值，如果目前的数大于或等于发现至今最大的。

Working code

int count2(int *p, int n) { 
    int max = -1000; //this variable represents negative infinity. 
    int cnt = 0; 
    int i; 
    for(i = n-1; i >=0; i--) { 
     if(p[i] >= max){ 
      cnt++; 
     } 
     if(p[i] > max){ 
      max = p[i]; 
     } 
    } 
    return cnt; 
} 

时间复杂度：O（n）的
空间复杂度：O（1）

Answer 5

是的，它可以在O(N)时间完成。我会给你一个关于如何去做的方法。如果我正确理解你的问题，你需要数组的数量大于数组中所有下一个元素的数量，只要维持顺序。

所以：

Let len = length of array x 

{...,x[i],x[i+1]...x[len-1]} 

We want the count of all elements x[i] such that x[i]> x[i+1] 
and so on till x[len-1] 

开始遍历从前端，即数组在i = len -1，并跟踪你所遇到的最大元素。

这可能是这样的：

max = x[len-1] //A sentinel max 

//Start a loop from i = len-1 to i = 0; 

if(x[i] > max) 
    max = x[i] //Update max as you encounter elements 

//Now consider a situation when we are in the middle of the array at some i = j 

{...,x[j],....x[len-1]} 

//Right now we have a value of max which is the largest of elements from i=j+1 to len-1 

因此，当你遇到一个x[j]比max大，你已经基本上发现，比旁边的所有元素更大的元素。你可以拥有一个计数器并在发生这种情况时增加计数。

伪代码显示算法的流程：

counter = 0 
i = length of array x - 1 
max = x[i] 
i = i-1 
while(i>=0){ 
     if(x[i] > max){ 
     max = x[i] //update max 
     counter++ //update counter 
     } 
     i-- 
} 

所以最终counter将有您所需要的元素数量。

希望我能解释你如何去做这件事。编码这应该是一个有趣的练习作为一个起点。