다음 더 많은 수의 Q 쿼리 인쇄

난이도 중급
자주 묻는 질문 아마존 팩트 셋 광신자
배열 스택조회수 23

Print Next Greater Number of Q query 문제에서 우리는 정렬 숫자를 포함하는 크기 n의 a [] 및 쿼리를 나타내는 크기 m의 또 다른 배열 q []. 각 쿼리는 배열 a []의 인덱스를 나타냅니다. 각 쿼리에 대해 인덱스 q [i]의 숫자보다 다음으로 큰 배열 a []의 숫자를 인쇄합니다.

다음 더 많은 수의 Q 쿼리 인쇄

입력 

a [] = {3, 4, 2, 7, 5, 8, 10, 6}

q [] = {3, 6, 1}

산출

8 -1 7

입력 

a [] = {4, 7, 9, 8}

q [] = {1, 2}

산출

9 - 1

순진한 방법

암호알고리즘

  1. n 크기의 배열 a []와 쿼리를 나타내는 m 크기의 배열 q []를 초기화합니다.
  2. 0에서 m-1로 이동하고 q [i] +1에서 n-1까지 내부 루프를 만듭니다. 배열 a []의 현재 인덱스에있는 요소가 q [i]와 같은 인덱스에있는 요소보다 큰지 확인하고 배열 a []의 현재 인덱스에있는 요소를 인쇄합니다.
  3. 쿼리 인덱스의 요소 뒤에 배열에 더 큰 요소가 없으면 -1을 인쇄합니다.

다음으로 많은 수의 Q 쿼리를 인쇄하는 C ++ 프로그램

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

void next_greatest(int a[], int n, int q[], int m){ 
    
    for(int i=0; i<m; i++){
        
        for(int j=q[i]+1; j<n; j++){
            
            if(a[j]>a[q[i]]){
                cout<<a[j]<<" ";
                break;
            }
            
            if(j==n-1){
                cout<<"-1 ";
            }
        }
    }
} 

int main(){ 
    int a[] = {3, 4, 2, 7, 5, 8, 10, 6}; 
    int n = sizeof(a) / sizeof(a[0]); 
    
    int q[] = {3, 6, 1}; 
    int m = sizeof(q) / sizeof(q[0]); 
    
    next_greatest(a, n, q, m);
    
    return 0;
}
8 -1 7

다음으로 많은 수의 Q 쿼리를 인쇄하는 Java 프로그램

import java.util.*;

class nextGreatest{
    
    static void next_greatest(int[] a, int n, int[] q, int m){ 
    
        for(int i=0; i<m; i++){
            
            for(int j=q[i]+1; j<n; j++){
                
                if(a[j]>a[q[i]]){
                    System.out.print(a[j]+" ");
                    break;
                }
                
                if(j==n-1){
                    System.out.print("-1 ");
                }
            }
        }
    } 

  public static void main (String[] args){
      
    int[] a = {3, 4, 2, 7, 5, 8, 10, 6}; 
        int n = a.length; 
        
        int[] q = {3, 6, 1}; 
        int m = q.length; 
        
        next_greatest(a, n, q, m);
  }
}
8 -1 7

복잡성 분석

시간 복잡성 : O (m * n) 여기서 n은 배열 a []의 요소 수이고 m은 배열 q []의 요소 수입니다.

보조 공간 : O (1) 우리는 일정한 추가 공간을 사용하기 때문입니다.

효율적인 방법

암호알고리즘

  1. n 크기의 배열 a []와 쿼리를 나타내는 m 크기의 배열 q []를 초기화합니다.
  2. 배열 next []를 생성하여 다음 요소를 스택에 저장하고 0을 그 안에 푸시합니다.
  3. 1에서 n-1로 이동하고 스택이 비어 있는지 확인하고 현재 인덱스 또는 i 값을 그 안에 넣습니다.
  4. 그렇지 않으면 스택이 비어 있지 않은 동안 현재 인덱스에있는 배열 a []의 요소가 스택의 인덱스 맨 위에있는 요소보다 크거나 같은지 확인하십시오. update-index가 배열 next [] 스택의 맨 위와 같은지 확인하십시오. 현재 인덱스를 선택하고 상단을 팝하고 그렇지 않으면 루프를 끊습니다.
  5. 스택이 비어 있지 않은 상태에서 다시 탐색하십시오. update-index는 배열 스택의 맨 위와 같습니다. next []를 -1로하고 맨 위를 팝하십시오.
  6. 0에서 m-1로 이동하고 q [i]와 같은 위치에서 next [] 배열에 저장된 인덱스에 해당하는 배열 a []의 요소를 인쇄합니다.

다음으로 많은 수의 Q 쿼리를 인쇄하는 C ++ 프로그램

#include <bits/stdc++.h> 
using namespace std; 
void next_greatest(int next[], int a[], int n){ 
    stack<int> s; 
    s.push(0);  
    for(int i = 1; i < n; i++)
    {   
        while(!s.empty()){   
            int cur = s.top();  
            if(a[cur] < a[i]){                   
                next[cur] = i;   
                s.pop(); 
            }  
            else{
                break;
            }    
        } 
        s.push(i); 
    }  
    while(!s.empty()){ 
        int cur = s.top(); 
        next[cur] = -1; 
        s.pop(); 
    } 
} 
void answer_query(int a[], int next[], int n, int q[], int m){ 
    for(int i=0; i<m; i++){
        int position = next[q[i]]; 
      
        if(position == -1){ 
            cout<<-1<<" "; 
        }    
      
        else{
            cout<<a[position]<<" ";
        }    
    }
} 
  
int main(){ 
  
    int a[] = {3, 4, 2, 7, 5, 8, 10, 6}; 
    int n = sizeof(a) / sizeof(a[0]); 
    
    int q[] = {3, 6, 1};
    int m = sizeof(q) / sizeof(q[0]); 
  
    int next[n] = { 0 }; 
  
    next_greatest(next, a, n); 
  
    answer_query(a, next, n, q, m); 
 
    return 0; 
}
8 -1 7

다음으로 많은 수의 Q 쿼리를 인쇄하는 Java 프로그램

import java.util.*; 

class NextGreatest{ 
    public static int[] next_greatest(int a[], int q[]){ 
        int ans[] = new int[a.length];
        
        Stack<Integer> s = new Stack<>(); 
        s.push(a[0]); 
        int j = 0; 
        for(int i = 1; i < a.length; i++){ 
            int next = a[i]; 
            
            if(!s.isEmpty()){ 
                int element = s.pop(); 
                
                while(next > element){ 
                    ans[j] = next; 
                    j++; 
                    if(s.isEmpty()) 
                        break; 
                    element = s.pop(); 
                } 
                
                if(element > next) 
                    s.push(element); 
            } 
            s.push(next); 
        }
        
        while(!s.isEmpty()){ 
            int element = s.pop(); 
            ans[j] = -1; 
            j++; 
        } 
        
        return ans; 
    } 
    
    public static void main(String[] args){ 
        int a[] = {3, 4, 2, 7, 5, 8, 10, 6}; 
        int q[] = {3, 6, 1}; 
        int ans[] = next_greatest(a,q); 
        
        for(int i = 0; i<q.length; i++){ 
            System.out.print(ans[q[i]] + " "); 
        } 
    } 
}
8 -1 7

복잡성 분석

시간 복잡성 : max (O (n), O (m)), O (n)은 다음 요소에 대한 배열을 사전 처리하고 각 쿼리에는 일정한 시간, 즉 O (1)이 필요합니다.

보조 공간 : O (n) 여기서 n은 배열 a []의 요소 수입니다.

참조

Translate »