다음 더 큰 요소 I Leetcode 솔루션

난이도 쉽게
자주 묻는 질문 아마존 블룸버그 게시물에서
알고리즘 코딩 인터뷰 인터뷰 준비 리트코드 LeetCodeSolutions 스택조회수 90

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

문제 정책

이 문제에서는 첫 번째 목록이 두 번째 목록의 하위 집합 인 두 개의 목록이 제공됩니다. 첫 번째 목록의 각 요소에 대해 두 번째 목록에서 다음으로 큰 요소를 찾아야합니다.

다음 더 큰 요소 I Leetcode 솔루션

nums1 = [4,1,2], nums2 = [1,3,4,2]
[-1,3,-1]

설명 :

list1의 첫 번째 요소, 즉 4의 경우 list2에는 다음으로 큰 요소가 없으므로 그 답은 -1입니다.
list1의 두 번째 요소, 즉 1의 경우 목록 3에서 1보다 큰 2이 있으므로 그 답은 3입니다.
list1의 세 번째 요소, 즉 2의 경우 list2에 다음으로 큰 요소가 없으므로 그 답은 -1입니다.

nums1 = [2,4], nums2 = [1,2,3,4]
[3,-1]

접근 1 (Brute Force)

이 접근 방식에서는 중첩 된 for 루프를 사용하여 list1에서 선형 순회를 수행하여 list2의 각 요소에 대해 다음으로 큰 요소를 간단히 찾습니다.
list1의 각 요소는 먼저 list2에서 검색된 다음 그 다음으로 큰 요소가 검색됩니다. 플래그 변수를 사용하여이를 수행합니다. list1의 각 요소에 대해 먼저 false로 설정됩니다. list2에서 요소를 찾으면 true로 설정됩니다. 그 후 다음 더 큰 것을 찾을 때 다시 false로 설정합니다. 이렇게하면 해당 변수에 대해 list2에 다음으로 큰 요소가 있는지 또는 없는지 알 수 있습니다.

  • 플래그 변수가 참이면 해당 요소에 대해 다음으로 큰 값을 찾을 수 없음을 의미합니다.
  • 플래그 변수가 거짓이면 해당 요소에 대해 다음으로 큰 값을 찾았다는 의미입니다.

따라서 각 내부 루프의 끝에 플래그 값에 따라 답변으로 -1을 삽입합니다.

차세대 요소 I Leetcode 솔루션 구현

C ++ 프로그램

#include <iostream>
#include <vector>
using namespace std;
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        vector<int> ans;
        for(int i=0;i<nums1.size();i++){
            bool flag=false;
            for(int j=0;j<nums2.size();j++){
                if(nums1[i]==nums2[j])flag=true;
                if(flag && nums1[i]<nums2[j]){
                    ans.push_back(nums2[j]);flag=false;break;
                }
            }
            if(flag)ans.push_back(-1);
            
        }
        return ans;
    }
int main()
{
    vector<int> nums1{ 4,1,2 }; 
    vector<int> nums2{ 1,3,4,2 }; 
    vector<int>ans=nextGreaterElement(nums1,nums2);
    for(int i=0;i<ans.size();i++){
        cout<<ans[i]<<" ";
    }
}
-1 3 -1

자바 프로그램

import java.util.*;
import java.lang.*;

class Solution
{  
    public static void main(String args[])
    {
        int[]nums1={4,1,2};
        int[]nums2={1,3,4,2};
        int[]ans=nextGreaterElement(nums1,nums2);
        for(int i:ans){
            System.out.print(i+" ");
        }
            
        
    }
    public static int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int[]ans=new int[nums1.length];
        for(int i=0;i<nums1.length;i++){
            boolean flag=false;
            for(int j=0;j<nums2.length;j++){
                if(nums1[i]==nums2[j])flag=true;
                if(flag && nums1[i]<nums2[j]){
                    ans[i]=nums2[j];flag=false;break;
                }
            }
            if(flag)ans[i]=-1;
            
        }
        return ans;
    }
}
-1 3 -1

차세대 요소 I Leetcode 솔루션에 대한 복잡성 분석

시간 복잡성

O (m * n) : nums1의 각 요소에 대해 nums2를 왼쪽에서 오른쪽으로 선형으로 이동합니다. 따라서 시간 복잡도는 O (m * n)이며 여기서 m과 n은 목록의 길이입니다.

공간 복잡성 

O (1) : 추가 공간이 사용되지 않습니다 (ANS 배열에 사용 된 공간은 필요하기 때문에 고려되지 않습니다).

접근 방식 2 (스택 사용)

이 접근 방식은 두 부분으로 구성됩니다.
첫째, 스택을 사용하여 선형 시간에서 list2의 각 요소에서 다음으로 큰 요소를 가져옵니다. 각 요소의 다음으로 큰 요소는 지도.
둘째, map을 사용하여 list1의 각 요소에 대한 답변을 답변 배열에 저장합니다.

따라서 list2를 탐색하고 현재 숫자보다 작은 스택 상단의 모든 요소를 ​​반복적으로 팝하고 동시에 각 팝에서 현재 요소를 팝된 각 요소의 가장 가까운 큰 답변으로 기록합니다. 이 매핑에서는 단순히지도를 사용합니다.
이제 우리는 그 다음으로 큰 요소를 가진 요소의 매핑 일 뿐인 맵을 가지고 있습니다.
마지막으로 list1을 탐색하고 맵의 각 값을 답변 목록에 저장합니다.

차세대 요소 I Leetcode 솔루션 구현

C ++ 프로그램

#include <iostream>
#include <vector>
#include <stack>
#include <map>
using namespace std;
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        stack<int>stack;
        map<int,int>map;
        vector<int>ans;
        for(int i=0;i<nums2.size();i++){
            while(!stack.empty()){
                if(stack.top()<nums2[i]){
                    map.insert(pair<int,int>(stack.top(),nums2[i]));
                    stack.pop();
                }else break;
            }
            stack.push(nums2[i]);
        }
        
        for(int i=0;i<nums1.size();i++){
            int val = map[nums1[i]];
            if(val==0)ans.push_back(-1);
            else ans.push_back(val);
        }
        return ans;
    }
int main()
{
    vector<int> nums1{ 4,1,2 }; 
    vector<int> nums2{ 1,3,4,2 }; 
    vector<int>ans=nextGreaterElement(nums1,nums2);
    for(int i=0;i<ans.size();i++){
        cout<<ans[i]<<" ";
    }
}
-1 3 -1

자바 프로그램

import java.util.*;
import java.lang.*;

class Solution
{  
    public static void main(String args[])
    {
        int[]nums1={4,1,2};
        int[]nums2={1,3,4,2};
        int[]ans=nextGreaterElement(nums1,nums2);
        for(int i:ans){
            System.out.print(i+" ");
        }
            
        
    }
    public static int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Stack<Integer>stack=new Stack<Integer>();
        Map<Integer,Integer>map=new HashMap<Integer,Integer>();
        int[]ans=new int[nums1.length];
        for(int i:nums2){
            while(!stack.isEmpty()){
                if(stack.peek()<i){
                    map.put(stack.peek(),i);
                    stack.pop();
                }else break;
            }
            stack.push(i);
        }
        for(int i=0;i<nums1.length;i++){
            if(map.containsKey(nums1[i]))
            ans[i]=map.get(nums1[i]);
            else ans[i]=-1;
        }
        return ans;
    }
}
-1 3 -1

차세대 요소 I Leetcode 솔루션에 대한 복잡성 분석

시간 복잡성

O (m + n) : 첫째, list2의 모든 요소에 대해 다음으로 큰 요소를 찾기 위해 list2를 순회합니다. 그런 다음 list1을 탐색하여 답변을 추가합니다. 따라서 시간 복잡도는 두 목록 길이의 합계입니다.

공간 복잡성 

의 위에): 우리는지도를 사용하여 O (1) 시간의 모든 키에 대한 답을 찾고 있으므로 공간 복잡성은 O (n)입니다.

균열 시스템 설계 인터뷰
Translate »
1