နောက်ထပ်သာလွန်သော Element I Leetcode Solution


ခက်ခဲအဆင့် လွယ်ကူသော
မကြာခဏမေးတယ် အမေဇုံ ဘလွန်းဘာ့ဂ်
စုပုံထား

ပြProbleနာဖော်ပြချက်

ဤပြproblemနာတွင်ကျွန်ုပ်တို့အားပထမစာရင်းသည်ဒုတိယစာရင်း၏အစိတ်အပိုင်းတစ်ခုဖြစ်သည်။ ပထမ ဦး ဆုံးစာရင်း၏ဒြပ်စင်တစ်ခုစီအတွက်၊ ဒုတိယစာရင်းရှိနောက်ထပ် ပို၍ ကြီးမားသောဒြပ်စင်ကိုကျွန်ုပ်တို့ရှာဖွေရမည်။

နောက်ထပ်သာလွန်သော Element I Leetcode Solution

နမူနာ

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

ရှင်းလင်းချက်:

list1 ရဲ့ပထမ element အတွက်ဆိုလိုတာက 4 အတွက်နောက်ထပ် list2 မှာနောက်တစ်ခုမရှိတော့ဘူး။
list1 ၏ဒုတိယဒြပ်စင်အတွက်ဆိုလိုသည်မှာ ၁ တွင်စာရင်း ၂ တွင် ၁ ထက်ကြီးသော ၃ ခုရှိခြင်းကြောင့်အဖြေသည် ၃ ဖြစ်သည်။
list1 ရဲ့တတိယ element အတွက်ဆိုလိုတာက 2 အတွက်နောက်ထပ် list2 မှာနောက်ထပ်မရှိတော့ဘူး၊

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

ချဉ်းကပ်နည်း 1 (Brute Force)

ဤချဉ်းကပ်မှုတွင် list1 ၏ element တစ်ခုချင်းစီအတွက်နောက်ထပ်ပိုမိုကြီးမားသော element တစ်ခုကိုရှာရန် list2 တွင် linear ဖြတ်သန်းခြင်းအားဖြင့် nested loop ကိုအသုံးပြုသည်။
list1 ၏ element တစ်ခုချင်းစီကို list2 တွင် ဦး စွာရှာဖွေပြီးနောက်၎င်းနောက်၎င်း၏နောက်ထပ်ကြီးမားသော element ကိုရှာဖွေသည်။ ကျွန်ုပ်တို့သည် flag variable တစ်ခုကိုအသုံးပြုခြင်းအားဖြင့်၎င်းကိုပြုလုပ်နေသည်။ list1 ရဲ့ element တစ်ခုချင်းစီအတွက်တော့ first ကို false အဖြစ်သတ်မှတ်ပါတယ်။ list2 ထဲက element ကိုတွေ့ပြီဆိုရင်၊ true ဖြစ်သွားပြီ။ ပြီးတဲ့နောက်၊ နောက်ထပ်ကြီးတဲ့အရာတစ်ခုကိုတွေ့ပြီဆိုရင်၊ အဲဒါကို false အဖြစ်ပြန်သတ်မှတ်ပါလိမ့်မယ်။ အဲဒီလိုလုပ်ခြင်းအားဖြင့်ကျွန်တော်တို့ဟာ list2 မှာနောက်ထပ် variable တစ်ခုထပ်ရှိသေးတယ်ဆိုတာသိရလိမ့်မယ်။

  • အကယ်၍ flag variable သည်မှန်လျှင်၊ ၎င်း element အတွက်နောက်ထပ်တန်ဖိုးကိုကျွန်ုပ်တို့မတွေ့နိုင်တော့ဟုဆိုလိုသည်။
  • အကယ်၍ flag variable သည် false ဖြစ်ပါက၎င်း element အတွက်နောက်ထပ်တန်ဖိုးတစ်ခုထပ်မံတွေ့ပြီဖြစ်သည်။

ထို့ကြောင့်ကွင်းဆက်တစ်ခုစီ၏အဆုံးတွင် flag value အရကျွန်ုပ်တို့သည် -1 ကိုအဖြေအဖြစ်ထည့်ပါလိမ့်မည်။

နောက်ထပ်သာလွန်သော Element I Leetcode Solution အတွက်အကောင်အထည်ဖော်ခြင်း

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

Next Greater Element I Leetcode Solution အတွက်ရှုပ်ထွေးမှုအားခွဲခြမ်းစိတ်ဖြာခြင်း

အချိန်ရှုပ်ထွေး

အို (မီတာ * n) nums1 ၏ element တစ်ခုစီအတွက်ကျွန်ုပ်တို့သည် nums2 ကိုဘယ်ဘက်မှညာသို့သွားနေကြသည်။ ထို့ကြောင့်အချိန်ရှုပ်ထွေးမှုသည်အို (မီတာ * n) ဖြစ်ပြီးမီတာနှင့် lists သည်စာရင်းအရှည်များဖြစ်သည်။

အာကာသရှုပ်ထွေးမှု 

အို (၁) အပိုနေရာမရှိ (ans ခင်းကျင်းအတွက်အသုံးပြုသောအကွာအဝေးကိုလိုအပ်သောကြောင့်ထည့်သွင်းစဉ်းစား) ။

ချဉ်းကပ်နည်း ၁ (ပုံကို သုံး၍)

ဒီချဉ်းကပ်မှုအပိုင်းနှစ်ပိုင်းပါဝင်သည်။
ပထမ ဦး စွာကျွန်ုပ်တို့သည် linear2 တွင် listXNUMX ၏ element တစ်ခုစီ၏နောက်ထပ်သာလွန်သော element တစ်ခုကိုရရှိရန် stack ကိုအသုံးပြုနေသည်။ တစ်ခုချင်းစီ၏နောက်သာ။ ကြီးသောဒြပ်စင်ကို a ထဲတွင်သိမ်းဆည်းထားသည် မြေပုံ.
ဒုတိယအချက်အနေဖြင့် list1 ၏ element တစ်ခုချင်းစီအတွက်အဖြေကိုမြေပုံကို သုံး၍ ကျွန်ုပ်တို့၏အဖြေခင်းကျင်းမှုတွင်သိမ်းဆည်းလိမ့်မည်။

ထို့ကြောင့်ကျွန်ုပ်တို့သည် list2 ကိုဖြတ်သန်းသွားပြီးလက်ရှိနံပါတ်များထက်သေးငယ်ပြီးတစ်ပြိုင်နက်တည်းဖြစ်သော stack ထိပ်များမှ element များအားလုံးထပ်ခါတလဲလဲပေါ်လာလိမ့်မည်။ pop တစ်ခုစီတွင်လက်ရှိ element ကို popped element တစ်ခု၏အနီးဆုံးသာလွန်သောအဖြေအဖြစ်မှတ်တမ်းတင်လိမ့်မည်။ ဒီမြေပုံအတွက်မြေပုံကိုသာသုံးမည်။
ယခုတွင်ကျွန်ုပ်တို့တွင်မြေပုံရှိသည်။ ၎င်းသည်၎င်းတို့နှင့်သက်ဆိုင်သောနောက်ထပ်ပိုမိုကြီးမားသောဒြပ်စင်များနှင့်ဆက်စပ်နေသည်။
နောက်ဆုံးအနေဖြင့်ကျွန်ုပ်တို့သည် list1 ကိုဖြတ်ကျော်။ သူတို့၏သက်ဆိုင်ရာတန်ဖိုးများကိုမြေပုံမှကျွန်ုပ်တို့၏အဖြေစာရင်းတွင်သိမ်းဆည်းလိမ့်မည်။

နောက်ထပ်သာလွန်သော Element I Leetcode Solution အတွက်အကောင်အထည်ဖော်ခြင်း

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

Next Greater Element I Leetcode Solution အတွက်ရှုပ်ထွေးမှုအားခွဲခြမ်းစိတ်ဖြာခြင်း

အချိန်ရှုပ်ထွေး

အို (m + n) ပထမ ဦး စွာကျွန်ုပ်တို့သည် list2 ၏အစိတ်အပိုင်းအားလုံးအတွက်နောက်ထပ်ပိုမိုကြီးမားသောဒြပ်စင်ကိုရှာရန် list2 ကိုဖြတ်သန်းနေသည်။ ထို့နောက်ကျွန်ုပ်တို့သည်အဖြေများကိုဖြည့်စွက်ရန် list1 ကို ဖြတ်၍ သွားနေကြသည်။ ဒီတော့အချိန်ရှုပ်ထွေးမှုကစာရင်းနှစ်ခုလုံးရဲ့အရှည်စုစုပေါင်းဖြစ်တယ်။

အာကာသရှုပ်ထွေးမှု 

အို ()) အို (၁) အချိန်တွင်မည်သည့်သော့ချက်ကိုမဆိုကျွန်ုပ်တို့ရှာဖွေရန်မြေပုံကိုအသုံးပြုနေသဖြင့်နေရာအကျယ်အ ၀ န်းသည်အို (n) ဖြစ်သည်။