ווייַטער גרעסער אָפטקייַט עלעמענט  


שוועריקייט לעוועל מיטל
אָפט געבעטן אין אַקסענטורע קאַפּגעמיני מייקראָסאָפֿט UHG Optum
מענגע האַש אָנלייגן

אין דער ווייַטער גרעסער אָפטקייַט עלעמענט פּראָבלעם, מיר האָבן געגעבן אַ מענגע אַ [] פון גרייס N מיט נומערן. פֿאַר יעדער נומער אין די מענגע דרוק, די נומער איז רעכט אין אַ מענגע מיט אַ אָפטקייַט גרעסער ווי די קראַנט נומער.

ווייַטער גרעסער אָפטקייַט עלעמענטשפּילקע

בייַשפּיל  

אַרייַנשרייַב 

אַ [] = {1, 1, 2, 3, 4, 2, 1}

רעזולטאַט 

-1 -1 1 2 2 1 -1

אַרייַנשרייַב

אַ [] = {1, 1, 2, 3}

רעזולטאַט

-1 -1 -1 -1

אַלגאָריטהם  

איצט מיר וויסן די פּראָבלעם ויסזאָגונג פֿאַר דער ווייַטער גרעסער פרעקווענסי עלעמענט פּראָבלעם. אַזוי, מיר מאַך צו זיין אַלגערידאַם.

  1. יניטיאַליזירן אַ מענגע a [] פון גרייס n.
  2. שאַפֿן אן אנדער מענגע פרעק [] פון גרייס INT16_MAX צו קראָם די אָפטקייַט און יניטיאַליזירן עס ווי 0.
  3. אַריבער די מענגע אַ [] און ינקראַמאַנט די ווערט אין מענגע פרעק [] ביי אינדעקס a [איך].
  4. שאַפֿן אַ סטאַק s און שטופּן 0 אין עס און אַ פּלאַץ פון גרייס N צו קראָם די רעזולטאַט.
  5. דורכגיין פון 1 צו n-1 און קאָנטראָלירן צי ווערט ביי פרעק [a [s.top ()]] איז גרעסער ווי ווערט ביי פרעק [אַ [i]], שטופּט די איצטיקע שטעלע / i אין אָנלייגן.
  6. אַנדערש ווען ווערט ביי פרעק [a [s.top ()]] איז ווייניקער ווי ווערט ביי freq [a [i]] און אָנלייגן איז נישט ליידיק, דערהייַנטיקן רעז ווי רעס [s.top ()] = אַ [i] און קנאַל די שפּיץ. שטופּן די קראַנט שטעלע / איך אין אָנלייגן.
  7. בשעת סטאַק איז נישט ליידיק, דערהייַנטיקן די רעס ווי res [s.top ()] = -1 און קנאַל די שפּיץ.
  8. דרוק דעם מענגע רעז [].

C ++ פּראָגראַם פֿאַר ווייַטער גרעסער פרעקווענסי עלעמענט  

#include <bits/stdc++.h>
using namespace std; 

void NextGreaterFrequency(int a[], int n, int freq[]){ 
  
    stack<int> s;  
    s.push(0); 
      
    int res[n] = {0};
    
    for(int i = 1; i < n; i++){ 
        if(freq[a[s.top()]] > freq[a[i]]){ 
            s.push(i); 
        }    
        else{ 
            while((freq[a[s.top()]] < freq[a[i]]) && !s.empty()){ 
                res[s.top()] = a[i]; 
                s.pop(); 
            } 
            
            s.push(i); 
        } 
    } 
  
    while(!s.empty()){ 
        res[s.top()] = -1; 
        s.pop(); 
    } 
    for(int i = 0; i < n; i++){ 
        cout<<res[i]<<" "; 
    } 
} 
  
int main(){ 
  
    int a[] = {1, 1, 2, 3, 4, 2, 1}; 
    int n = sizeof(a)/sizeof(a[0]); 
    int max = INT16_MAX; 
    
    for(int i = 0; i < n; i++){ 
        if (a[i] > max){ 
            max = a[i]; 
        } 
    } 
    int freq[max + 1] = {0}; 
      
    for(int i = 0; i < n; i++){ 
        freq[a[i]]++; 
    } 
  
    NextGreaterFrequency(a, n, freq); 
    return 0; 
}
-1 -1 1 2 2 1 -1

Java פּראָגראַם פֿאַר ווייַטער גרעסער פרעקווענסי עלעמענט  

import java.util.*; 

class ngf{ 

    static void NextGreaterFrequency(int a[], int n, int freq[]){ 
    
        Stack<Integer> s = new Stack<Integer>();  
        s.push(0); 
        
        int res[] = new int[n]; 
        for(int i = 0; i < n; i++){ 
            res[i] = 0; 
        }
        
        for(int i = 1; i < n; i++){ 
        
            if(freq[a[s.peek()]] > freq[a[i]]){ 
                s.push(i); 
            }
            
            else{ 
                while (freq[a[s.peek()]] < freq[a[i]] && s.size()>0){ 
                    res[s.peek()] = a[i]; 
                    s.pop(); 
                } 
                
                s.push(i); 
            } 
        } 
        
        while(s.size() > 0){ 
            res[s.peek()] = -1; 
            s.pop(); 
        } 
        
        for(int i = 0; i < n; i++){ 
            System.out.print( res[i] + " "); 
        } 
    } 
    
    public static void main(String args[]){ 
    
        int a[] = {1, 1, 2, 3, 4, 2, 1}; 
        int n = a.length; 
        int max = Integer.MIN_VALUE;
        
        for(int i = 0; i < n; i++){ 
            if(a[i] > max){ 
                max = a[i]; 
            } 
        } 
        int freq[] = new int[max + 1]; 
        
        for(int i = 0; i < max + 1; i++){ 
            freq[i] = 0; 
        }
        
        for(int i = 0; i < n; i++){ 
            freq[a[i]]++; 
        } 
        
        NextGreaterFrequency(a, n, freq); 
    } 
}
-1 -1 1 2 2 1 -1

קאַמפּלעקסיטי אַנאַליסיס  

צייט קאַמפּלעקסיטי: אָ (n) ווו n איז די number פון עלעמענטן אין די מענגע אַ []. מיר נוצן איין אָנלייגן און אַ מענגע פֿאַר סטאָרינג די לעצט ענטפער.

זע אויך
גער אַ מענגע צו רידוסט פאָרעם

אָרט קאַמפּלעקסיטי: אָ (מאַקס) ווו מאַקס איז גלייַך צו INT16_MAX. דאָ די ווערט פון מאַקס איז פאַרפעסטיקט וואָס איז 32767. מיר מאַכן אַ אָפטקייַט מענגע צו קראָם די ציילן פון די נומער אין די ינפּוט מענגע.

רעפֿערענצן