องค์ประกอบความถี่ที่ยิ่งใหญ่ถัดไป  


ระดับความยาก กลาง
ถามบ่อยใน แอคเซนเจอร์ Capgemini ไมโครซอฟท์ 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

ขั้นตอนวิธี  

ตอนนี้เราทราบคำชี้แจงปัญหาสำหรับปัญหา Next Greater Frequency Element แล้ว ดังนั้นเราจึงมุ่งไปที่อัลกอริทึมของมัน

  1. เริ่มต้นอาร์เรย์ a [] ขนาด n
  2. สร้างความถี่อาร์เรย์ [] ขนาด INT16_MAX อื่นเพื่อเก็บความถี่และเริ่มต้นเป็น 0
  3. สำรวจอาร์เรย์ a [] และเพิ่มค่าในความถี่ของอาร์เรย์ [] ที่ดัชนี a [i]
  4. สร้างสแต็ก s และกด 0 ในนั้นและอาร์เรย์ความละเอียดขนาด n เพื่อเก็บผลลัพธ์
  5. เคลื่อนที่จาก 1 ไปยัง n-1 และตรวจสอบว่าค่าที่ freq [a [s.top ()]] มากกว่าค่าที่ความถี่ [a [i]] ให้ดันตำแหน่งปัจจุบัน / i ในสแตก
  6. ในขณะที่ค่าที่ freq [a [s.top ()]] น้อยกว่าค่าที่ freq [a [i]] และสแต็กไม่ว่างให้อัพเดต res เป็น res [s.top ()] = a [i] และ ปรากฏด้านบน ดันตำแหน่งปัจจุบัน / i ในสแต็ก
  7. ในขณะที่สแต็กไม่ว่างให้อัปเดต res เป็น res [s.top ()] = -1 และแสดงด้านบน
  8. พิมพ์อาร์เรย์ res []

โปรแกรม 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

การวิเคราะห์ความซับซ้อน  

ความซับซ้อนของเวลา: O (n) โดยที่ n คือ number ขององค์ประกอบในอาร์เรย์ a [] เราใช้สแต็กและอาร์เรย์หนึ่งชุดสำหรับเก็บคำตอบสุดท้าย

ดูสิ่งนี้ด้วย
แปลงอาร์เรย์เป็นรูปแบบย่อ

ความซับซ้อนของอวกาศ: O (สูงสุด) โดยที่สูงสุดเท่ากับ INT16_MAX ค่าสูงสุดได้รับการแก้ไขที่นี่คือ 32767 เราสร้างอาร์เรย์ความถี่เพื่อเก็บจำนวนจำนวนที่มีอยู่ในอาร์เรย์อินพุต

อ้างอิง