ធាតុប្រេកង់ធំជាងនេះបន្ទាប់


កម្រិតលំបាក មធ្យម
សួរញឹកញាប់ Accenture Capgemini ក្រុមហ៊ុន Microsoft យូអេសជីអុបទិក
អារេ ហាស់ ជង់

នៅក្នុងបញ្ហាធាតុប្រេកង់កាន់តែធំបន្ទាប់យើងបានផ្តល់អារេមួយនៃទំហំ n ដែលមានលេខ។ សម្រាប់លេខនីមួយៗនៅក្នុងឯកសារ អារេ ព្រីនលេខទៅវាត្រឹមត្រូវក្នុងអារេមួយដែលមានប្រេកង់ធំជាងលេខបច្ចុប្បន្ន។

ធាតុប្រេកង់ធំជាងនេះបន្ទាប់

ឧទាហរណ៍

បញ្ចូល 

a [] = {១, ១, ២, ៣, ៤, ២, ១}

ទិន្នផល 

-1 -1 1 2 2 1 1

បញ្ចូល

a [] = {១, ១, ២, ៣}

ទិន្នផល

-1 -1 -1 -1 -XNUMX -១ -XNUMX

ក្បួនដោះស្រាយ

ឥឡូវនេះយើងដឹងពីសេចក្តីថ្លែងការណ៍អំពីបញ្ហាហ្វ្រេកង់ហ្វ្រេកង់ហ្វ្រេកង់បន្ទាប់។ ដូច្នេះយើងឈានឆ្ពោះទៅរកក្បួនដោះស្រាយរបស់វា។

  1. ចាប់ផ្តើមអារេ a [] នៃទំហំ n ។
  2. បង្កើតអារេមួយផ្សេងទៀតនៃទំហំ INT16_MAX ដើម្បីផ្ទុកប្រេកង់និងចាប់ផ្តើមវាជា ០ ។
  3. ឆ្លងកាត់អារេ a [] និងបង្កើនតំលៃក្នុងអារេ freq [] នៅសន្ទស្សន៍ a [i] ។
  4. បង្កើតជង់ s និងរុញ 0 នៅក្នុងវានិងអារេនៃទំហំ n ដើម្បីរក្សាទុកលទ្ធផល។
  5. ឆ្លងកាត់ពី 1 ដល់ n-1 ហើយពិនិត្យមើលថាតើតម្លៃនៅ freq [a [s.top ()]] ធំជាងតម្លៃនៅ freq [a [i]] រុញទីតាំងបច្ចុប្បន្ន / អាយនៅក្នុងជង់។
  6. ផ្សេងទៀតខណៈពេលដែលតម្លៃនៅ freq [a [s.top ()]] គឺទាបជាងតម្លៃនៅ freq [a [i]] ហើយជង់គឺមិនទទេធ្វើបច្ចុប្បន្នភាព res ជា res [s.top ()] = a [i] និង លេចឡើងកំពូល។ រុញទីតាំងបច្ចុប្បន្ន / អាយនៅក្នុងជង់។
  7. ខណៈពេលដែលជង់មិនទទេធ្វើបច្ចុប្បន្នភាព res ជា 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

កម្មវិធីចាវ៉ាសម្រាប់ធាតុប្រេកង់ធំជាងមុន

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

ការវិភាគស្មុគស្មាញ

ស្មុគស្មាញពេលវេលា៖ O (n) ដែល n ជាកន្លែង number នៃធាតុនៅក្នុងអារេ a [] ។ យើងប្រើជង់មួយនិងអារេសម្រាប់រក្សាទុកចម្លើយចុងក្រោយ។

ស្មុគស្មាញអវកាស៖ O (អតិបរមា) ដែលអតិបរិមាស្មើនឹង INT16_MAX ។ នៅទីនេះតម្លៃអតិបរិមាត្រូវបានជួសជុលដែលមានចំនួន ៣២៧៦៧ ។ យើងបង្កើតអារេហ្វ្រេកង់ដើម្បីផ្ទុកចំនួនលេខដែលមាននៅក្នុងអារេបញ្ចូល។

ឯកសារយោង