如何查找數組中大於其後所有元素的元素數量？

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將有您所需要的元素數量。

希望我能解釋你如何去做這件事。編碼這應該是一個有趣的練習作爲一個起點。