다음 더 큰 주파수 요소

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

다음으로 더 큰 주파수 요소 문제에서는 숫자를 포함하는 n 크기의 배열 a []를 제공했습니다. 의 각 번호에 대해 정렬 인쇄하면 현재 숫자보다 빈도가 더 큰 배열에서 숫자가 오른쪽에 있습니다.

핀

예

입력 

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

산출 

-1 -1 1 2 2 -1

입력

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

산출

-1 -1 -1 -1

암호알고리즘

이제 우리는 다음 더 큰 주파수 요소 문제에 대한 문제 설명을 알고 있습니다. 그래서 우리는 알고리즘으로 이동합니다.

1. n 크기의 배열 a []를 초기화합니다.
2. 주파수를 저장하고 16으로 초기화하기 위해 INT0_MAX 크기의 또 다른 어레이 freq []를 생성합니다.
3. 배열 a []를 순회하고 인덱스 a [i]에서 배열 freq []의 값을 증가시킵니다.
4. 스택 s를 만들고 그 안에 0과 크기 n의 배열 res를 푸시하여 결과를 저장합니다.
5. 1에서 n-1로 이동하고 freq [a [s.top ()]]의 값이 freq [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 (max) 여기서 max는 INT16_MAX와 같습니다. 여기서 최대 값은 32767로 고정되어 있습니다. 입력 배열에있는 숫자의 개수를 저장하기 위해 주파수 배열을 만듭니다.

참조