ອົງປະກອບຄວາມຖີ່ສູງສຸດຕໍ່ໄປ


ລະດັບຄວາມຫຍຸ້ງຍາກ ຂະຫນາດກາງ
ຖາມເລື້ອຍໆໃນ Accenture Capgemini Microsoft UHG Optum
Array Hash Stack

ໃນບັນຫາອົງປະກອບຄວາມຖີ່ທີ່ຖັດໄປ, ພວກເຮົາໄດ້ໃຫ້ [] ຂອງຂະ ໜາດ n ປະກອບດ້ວຍຕົວເລກ. ສຳ ລັບແຕ່ລະເລກໃນ array ພິມ, ຈຳ ນວນທີ່ຖືກຕ້ອງໃນອາເລທີ່ມີຄວາມຖີ່ສູງກ່ວາ ຈຳ ນວນທີ່ຢູ່ໃນປະຈຸບັນ.

ອົງປະກອບຄວາມຖີ່ສູງສຸດຕໍ່ໄປ

ຍົກຕົວຢ່າງ

ການປ້ອນຂໍ້ມູນ 

a [] = {1, 1, 2, 3, 4, 2, 1}

ຜົນຜະລິດ 

-1 -1 1 2 2 1 1

ການປ້ອນຂໍ້ມູນ

a [] = {1, 1, 2, 3}

ຜົນຜະລິດ

-1 -1 -1 -1 -XNUMX -XNUMX -XNUMX -XNUMX -XNUMX -XNUMX -XNUMX -XNUMX -XNUMX -XNUMX -XNUMX -XNUMX -XNUMX -XNUMX -XNUMX -XNUMX

ລະບົບວິເຄາະ

ດຽວນີ້, ພວກເຮົາຮູ້ ຄຳ ຖະແຫຼງການບັນຫາ ສຳ ລັບປັນຫາຕໍ່ໄປຂອງຄວາມຖີ່ Next Greater Frequency Element. ດັ່ງນັ້ນ, ພວກເຮົາກ້າວໄປສູ່ລະບົບ algorithm ຂອງມັນ.

  1. ເລີ່ມຕົ້ນຂບວນ a [] ຂອງຂະ ໜາດ n.
  2. ສ້າງແບບອິດສະຫຼະ [] ຂອງຂະ ໜາດ INT16_MAX ເພື່ອເກັບຄວາມຖີ່ແລະເລີ່ມຕົ້ນເປັນ 0.
  3. Traverse ຂບວນ a [] ແລະເພີ່ມມູນຄ່າໃນ array freq [] ທີ່ index a [i].
  4. ສ້າງ stack s ແລະຍູ້ 0 ໃນມັນແລະແຖວຂອງຂະຫນາດ n ເພື່ອເກັບຜົນໄດ້ຮັບ.
  5. Traverse ຈາກ 1 ເຖິງ n-1 ແລະກວດເບິ່ງວ່າມູນຄ່າທີ່ freq [a [s.top ()]] ແມ່ນໃຫຍ່ກວ່າມູນຄ່າທີ່ freq [a [i]], ຍູ້ຕໍາແຫນ່ງໃນປະຈຸບັນ / i ຢູ່ໃນ stack.
  6. ອື່ນໃນຂະນະທີ່ມູນຄ່າທີ່ freq [a [s.top ()]] ແມ່ນຫນ້ອຍກ່ວາມູນຄ່າທີ່ freq [a [i]] ແລະ stack ບໍ່ແມ່ນຫວ່າງ, ປັບປຸງ res ເປັນ res [s.top ()] = a [i] ແລະ pop ເທິງ. ຍູ້ຕໍາແຫນ່ງ / i ໃນປະຈຸບັນໃນ stack.
  7. ໃນຂະນະທີ່ stack ບໍ່ຫວ່າງ, update res ເປັນ res [s.top ()] = -1 ແລະປ້ອນເທິງສຸດ.
  8. ພິມແຖວ array [].

ໂປຣແກຣມ 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 Program for Next Greater Frequency Element

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. ນີ້ແມ່ນຄ່າຂອງສູງສຸດທີ່ຖືກ ກຳ ນົດເຊິ່ງແມ່ນ 32767. ພວກເຮົາສ້າງຕາຕະລາງຄວາມຖີ່ເພື່ອເກັບຮັກສາ ຈຳ ນວນຕົວເລກທີ່ມີຢູ່ໃນແຖວເຂົ້າ.

ເອກະສານ