מספר ה- NGE לימין


רמת קושי קַל
נשאל לעתים קרובות נאמן קנאות פורקיטים
מערך תכנות דיאמי בליל לערום

במספר ה- NGE לבעיה הנכונה נתנו מערך a] מספר גודל n ו- q של שאילתות המייצגות את אינדקס המערך. עבור כל שאילתה, אני מדפיס את המספר הכולל של אלמנטים גדולים יותר הבאים שזה נכון.

מספר ה- NGE לימין

דוגמה

קֶלֶט

a [] = {3, 4, 2, 7, 5, 8, 10, 6}

q1 = 0

q2 = 5

תְפוּקָה 

4

1

קֶלֶט 

a [] = {1, 2, 3, 4, 5, 6, 7}

q1 = 0

תְפוּקָה 

6

שיטה נאיבית

אַלגוֹרִיתְם

  1. אתחל מערך a [] בגודל n.
  2. צור משתנה c כדי לספור את ה- NGE ולאתחל אותו כ- 0.
  3. צור משתנה lastEle ושמור את הערך של המערך a [] באינדקס q כלומר שאילתה בו.
  4. חצה מ q + 1 עד n-1 ובדוק אם הערך של מערך a [] באינדקס הנוכחי גדול מ- lastEle, עדכן את lastEle כערך של מערך a [] באינדקס הנוכחי. הגדל את הספירה.
  5. הדפיסו את הספירה.

C ++ תוכנית לספירת מספר ה- NGE מימין

#include <bits/stdc++.h> 
using namespace std; 
  
void count(int a[], int n, int q){ 
    int c = 0;
    int lastEle = a[q];
    
    for(int i=q+1; i<n; i++){
        if(a[i]>lastEle){
            lastEle = a[i];
            c++;
        }    
    }
    
    cout<<c<<endl;
} 
  
int main(){ 
    int a[] = {3, 4, 2, 7, 5, 8, 10, 6}; 
    int n = sizeof(a) / sizeof(a[0]); 
  
    count(a, n, 0); 
  
    count(a, n, 5); 
  
    return 0; 
}
4
1

תוכנית Java לספירת מספר ה- NGE ימינה

import java.util.*; 
  
class NGE{ 
  
    static void count(int a[], int n, int q){ 
        
        int c = 0;
        int lastEle = a[q];
        
        for(int i=q+1; i<n; i++){
            if(a[i]>lastEle){
                lastEle = a[i];
                c++;
            }    
        }
        
        System.out.println(c);
    } 
      
    public static void main(String args[]){ 
        int a[] = {3, 4, 2, 7, 5, 8, 10, 6}; 
        int n = a.length; 
      
        count(a, n, 0); 
      
        count(a, n, 5);
    } 
}
4
1

ניתוח מורכבות

מורכבות זמן: O (n) כאשר n הוא גודל המערך a [].

מרחב עזר: O (1) כי השתמשנו במרחב קבוע נוסף.

שיטה יעילה

אַלגוֹרִיתְם

  1. אתחל מערך a [] בגודל n המכיל מספרים ומערך dp באותו גודל.
  2. צור מערך הבא [] בגודל n והגדר את האלמנט שלו כ- 0.
  3. צור ערימה ודחף לתוכה 0.
  4. חצה בין 1 ל- n-1 ובעוד שהערימה אינה ריקה בדוק אם הערך במערך a [] באינדקס השווה לראש הערימה הוא פחות מהערך במערך a [] באינדקס הנוכחי, עדכן את הערך במערך הבא באינדקס השווה לראש הערמה כאינדקס נוכחי. פוצץ את החלק העליון של הערימה.
  5. אחרת לשבור את הלולאה.
  6. דחף את האינדקס הנוכחי בערימה.
  7. בעוד הערימה אינה ריקה, עדכן את הערך במערך הבא באינדקס השווה לראש הערימה כ -1. פוצץ את החלק העליון של הערימה.
  8. חצה דרך n-2 עד 0 ובדוק את הערך במערך הבא באינדקס הנוכחי הוא -1, עדכן את הערך במערך dp באינדקס הנוכחי כ 0. אחר כך ערך העדכון במערך הבא באינדקס הנוכחי כ -1 + dp [הבא [i] ].
  9. עבור כל שאילתה שווה ל- i אני מדפיס dp [I].

C ++ תוכנית לספירת מספר ה- NGE מימין

#include <bits/stdc++.h> 
using namespace std; 
  
void computeNext(int next[], int a[], int n){ 
    
    stack<int> s; 
  
    s.push(0); 
  
    for(int i = 1; i < n; i++){ 
  
        while(!s.empty()){ 
  
            int cur = s.top(); 
  
            if(a[cur] < a[i]){ 
                next[cur] = i; 
  
                s.pop(); 
            } 
  
            else{
                break;
            }    
        } 
  
        s.push(i); 
    } 
  
    while(!s.empty()){ 
  
        int cur = s.top(); 
  
        next[cur] = -1; 
  
        s.pop(); 
    } 
} 
  
void count(int a[], int dp[], int n){ 
     
    int next[n]; 
    memset(next, 0, sizeof(next)); 
  
    computeNext(next, a, n); 
  
    for(int i = n-2; i >= 0; i--){ 
  
        if(next[i] == -1){ 
            dp[i] = 0; 
        }    
  
        else{
            dp[i] = 1 + dp[next[i]]; 
        }    
    } 
} 
  
int answerQuery(int dp[], int index){ 
    return dp[index]; 
} 
  
int main(){ 
    int a[] = {3, 4, 2, 7, 5, 8, 10, 6}; 
    int n = sizeof(a) / sizeof(a[0]); 
  
    int dp[n]; 
  
    count(a, dp, n); 
  
    cout<<answerQuery(dp, 0)<<endl; 
  
    cout<<answerQuery(dp, 5)<<endl; 
  
    return 0; 
}
4
1

תוכנית Java לספירת מספר ה- NGE ימינה

import java.util.*; 
  
class NGE{ 
  
    static void computeNext(int next[], int a[], int n){ 
        
        Stack<Integer> s = new Stack<Integer>(); 
      
        s.push(0); 
      
        for(int i = 1; i < n; i++){ 
      
            while(s.size() > 0){ 
      
                int cur = s.peek(); 
      
                if(a[cur] < a[i]){ 
      
                    next[cur] = i; 
      
                    s.pop(); 
                } 
      
                else{
                    break;
                }    
            } 
      
            s.push(i); 
        } 
      
        while(s.size() > 0){ 
      
            int cur = s.peek(); 
      
            next[cur] = -1; 
      
            s.pop(); 
        } 
    } 
      
    static void count(int a[], int dp[], int n){ 
        
        int next[] = new int[n]; 
        for(int i = 0; i < n; i++){ 
            next[i] = 0; 
        }    
          
        computeNext(next, a, n); 
      
        for(int i = n-2; i >= 0; i--){ 
      
            if(next[i] == -1){ 
                dp[i] = 0; 
            }    
      
            else{
                dp[i] = 1 + dp[next[i]]; 
            }
        } 
    } 
      
    static int answerQuery(int dp[], int index){ 
        return dp[index]; 
    } 
      
    public static void main(String args[]){ 
        int a[] = {3, 4, 2, 7, 5, 8, 10, 6}; 
        int n = a.length; 
      
        int dp[] = new int[n]; 
      
        count(a, dp, n); 
      
        System.out.println(answerQuery(dp, 0)); 
      
        System.out.println(answerQuery(dp, 5)); 
    } 
}
4
1

ניתוח מורכבות

מורכבות זמן: O (1) מכיוון שכל השאילתות לוקחות זמן קבוע עקב חישובים מקדימים.

מרחב עזר: O (n) כאשר n הוא גודל המערך a [].

הפניות