Հաջորդ Greater Element I Leetcode լուծումը


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են Amazon Bloomberg
Գրապահոց

Խնդիրի հայտարարություն

Այս խնդրում մեզ տրվում է երկու ցուցակ, որոնցում առաջին ցուցակը երկրորդ ցուցակի ենթաբազմություն է: Առաջին ցուցակի յուրաքանչյուր տարրի համար մենք պետք է պարզենք երկրորդ ցուցակի հաջորդ ավելի մեծ տարրը:

Հաջորդ Greater Element I Leetcode լուծումը

Օրինակ

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

Բացատրությունը.

ցուցակի 1-ին տարրի համար, այսինքն `4-ի համար ցուցակում 2-ում չկա ավելի մեծ տարր, ուստի դրա պատասխանը -1 է:
1 ցուցակի երկրորդ տարրի համար, այսինքն 1-ի համար 3 ցուցակում 1-ը մեծ է 2-ից, ուստի դրա պատասխանը 3 է:
ցուցակի 1-ին տարրի համար, այսինքն `2-ի համար ցուցակում 2-ում չկա ավելի մեծ տարր, ուստի դրա պատասխանը -1 է:

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

Մոտեցում 1 (կոպիտ ուժ)

Այս մոտեցման մեջ մենք պարզապես գտնում ենք ցուցակի 1-ի յուրաքանչյուր տարրի հաջորդ ավելի մեծ տարրը `ցուցակում 2 կատարելով գծային անցում` օգտագործելով հանգուցային հանգույց:
List1- ի յուրաքանչյուր տարր նախ որոնվում է list2- ում, ապա հետագայում որոնվում է նրա հաջորդ ավելի մեծ տարրը: Մենք դա անում ենք դրոշի փոփոխականի միջոցով: Listանկ 1-ի յուրաքանչյուր տարրի համար այն նախ դրվում է կեղծ: Երբ մենք գտնում ենք տարրը ցուցակում 2, այն դրվում է true: Դրանից հետո, երբ գտնենք հաջորդ մեծին, այն նորից կեղծ կդնենք: Դրանով մենք կիմանանք, որ ցուցակի 2-ում կա ցանկացած հաջորդ մեծ տարր, կամ չկա:

  • Եթե ​​դրոշի փոփոխականը ճիշտ է, դա նշանակում է, որ մենք չենք կարող գտնել որևէ հաջորդ մեծ արժեք այդ տարրի համար:
  • Եթե ​​դրոշի փոփոխականը կեղծ է, նշանակում է, որ մենք գտել ենք մեկ այլ ավելի մեծ արժեք այդ տարրի համար:

Այսպիսով, յուրաքանչյուր ներքին օղակի վերջում, ըստ դրոշի արժեքի, մենք որպես պատասխան կտեղադրենք -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

Java ծրագիր

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

Բարդության վերլուծություն հաջորդ Greater Element- ի I Leetcode լուծման համար

Timeամանակի բարդություն

O (մ * ն): Nums1 յուրաքանչյուր տարրի համար մենք nums2- ը գծայինորեն անցնում ենք ձախից աջ: Այսպիսով, ժամանակի բարդությունը O է (m * n), որտեղ m և n ցուցակների երկարությունն են:

Տիեզերական բարդություն 

O (1): Օգտագործված ոչ մի լրացուցիչ տարածք (ans զանգվածի համար օգտագործված տարածությունը չի դիտարկվում, քանի որ դա անհրաժեշտ է):

Մոտեցում 2 (բուրգի օգտագործմամբ)

Այս մոտեցումը բաղկացած է երկու մասից:
Նախ, մենք օգտագործում ենք բուրգ ՝ ցուցակի 2-ի յուրաքանչյուր տարրի հաջորդ ավելի մեծ տարրը գծային ժամանակում ստանալու համար: Յուրաքանչյուր տարրի հաջորդ ավելի մեծ տարրը պահվում է ա-ում Քարտեզը.
Երկրորդ, մենք կպահպանենք ցուցակի 1 տարրի համար պատասխանը մեր պատասխանների զանգվածում `օգտագործելով քարտեզը:

Այսպիսով, մենք կանցնենք ցուցակը 2 և մի քանի անգամ դուրս կգանք բուրգի վերևից բոլոր տարրերը, որոնք ավելի փոքր են, քան ընթացիկ համարը և միաժամանակ, յուրաքանչյուր փոփում մենք կգրանցենք ընթացիկ տարրը որպես յուրաքանչյուր փչված տարրի ամենամոտ պատասխանը: Այս քարտեզագրման համար մենք պարզապես կօգտագործենք քարտեզ:
Այժմ մենք ունենք քարտեզ, որը պարզապես տարրերի քարտեզագրում է `իրենց համապատասխան հաջորդ մեծ տարրերով:
Վերջապես, մենք կկտրենք ցուցակը 1 և կպահենք դրանց համապատասխան արժեքները քարտեզից մեր պատասխանների ցուցակում:

Իրականացում Հաջորդ ավելի մեծ տարր 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

Java ծրագիր

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

Բարդության վերլուծություն հաջորդ Greater Element- ի I Leetcode լուծման համար

Timeամանակի բարդություն

O (m + n): Նախ, մենք անցնում ենք ցուցակը 2 ՝ ցուցակի բոլոր մյուս տարրերի համար հաջորդ ավելի մեծ տարր գտնելու համար: Դրանից հետո մենք անցնում ենք ցուցակը 2 ՝ պատասխանները կցելու համար: Այսպիսով, ժամանակի բարդությունը երկու ցուցակների երկարության գումարն է:

Տիեզերական բարդություն 

Վրա): Մենք օգտագործում ենք քարտեզ ՝ O (1) ժամանակի ցանկացած ստեղնի պատասխանը գտնելու համար, ուստի տարածության բարդությունը O (n) է: