بل لوی عنصر I د لیټکوډ حل


مشکل کچه په اسانۍ سره
په مکرر ډول دننه پوښتل کیږي ترلاسه کړئ Amazon د بلومبرګ
د دلۍ

ستونزه بیان

پدې ستونزه کې ، موږ ته دوه لیستونه راکړل شوي چې په هغې کې لومړی لیست د دوهم لیست ضمیمه ده. د لومړي لیست هر عنصر لپاره ، موږ باید په دوهم لیست کې بل لوی عنصر ومومئ.

بل لوی عنصر I د لیټکوډ حل

بېلګه

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 کې د خطي ټریورسال په کولو سره د لوپ لپاره د ځیر شوي ځای په کارولو سره.
د لیست 1 هر عنصر لومړی په لیست 2 کې لټول کیږي ، وروسته بیا د هغې بل لوی عنصر لټول کیږي. موږ دا د پرچم متغیرو په کارولو سره کوو. د لیست 1 هر عنصر لپاره ، دا لومړی غلط ته ټاکل شوی. کله چې موږ په لیست 2 کې عنصر وموند ، نو دا ریښتیا ټاکل کیږي. له هغې وروسته ، کله چې موږ به بل لوی وموندلو ، موږ به یې بیا غلط ته وتړو. د دې کولو په کولو سره ، موږ به پوه شو چې د دې تغیر لپاره په لیست 2 کې بل کوم بل لوی عنصر شتون لري یا هیڅ شتون نلري.

  • که چیرې د بیرغ متغیر ریښتینی وي ، نو پدې معنی چې موږ د دې عنصر لپاره هیڅ بل لوی ارزښت ونه موندل شو.
  • که چیرې د بیرغ متغیر غلط وي ، نو پدې معنی ده چې موږ د دې عنصر لپاره یو بل لوی ارزښت موندلی دی.

نو ، د هر داخلي لوپ په پای کې ، د بیرغ ارزښت سره سم به موږ د ځواب په توګه -1 دننه کړو.

د بل لوی عنصر I لیټکوډ حل لپاره پلي کول

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 لیټکوډ حل لپاره د پیچلو تحلیل

د وخت پیچلتیا

او (م * ن): د شمیره 1 هر عنصر لپاره موږ د شمیره 2 په مستقیم ډول له کی from څخه ښیې ته تعقیبوو. په دې توګه ، د وخت پیچلتیا د O (m * n) ده چیرې چې m او n د لیست اوږدوالی دی.

د ځای پیچلتیا 

O (1): هیڅ اضافي ځای کارول شوی ندی (د ځواب ویلونو لپاره ځای کارول شوی ندي ګ isn'tل کیږي ځکه چې دا اړین دی).

کړنالره 2 (د ګنډلو کارول)

دا کړنلاره دوه برخې لري.
لومړی ، موږ په لیکي وخت کې د لیست 2 هر عنصر راتلونکي لوی عنصر ترلاسه کولو لپاره یوه کڅوړه کار کوو. د هر عنصر راتلونکي لوی عنصر په a کې زیرمه کیږي نقشه.
دوهم ، موږ به د نقشې په کارولو سره زموږ په ځواب صف کې د لیست 1 هر عنصر لپاره ځواب ذخیره کړو.

نو ، موږ به لیست 2 وګرځوو او په مکرر ډول به ټول عناصر د پلیکنې پورتنۍ برخې څخه پوپ کړو چې د اوسني شمیر څخه کوچني دي او په ورته وخت کې ، په هر پاپ کې به موږ موجوده عنصر د هر پاپ شوي عنصر نږدې نږدې ځواب په توګه ثبت کړو. د دې نقشې لپاره ، موږ به ساده ډول نقشه وکاروو.
اوس ، موږ یوه نقشه لرو چې یوازې د عناصرو نقشه کول د دوی اړوند راتلونکي لوی عناصرو سره.
په نهایت کې ، موږ به لیست 1 وسوزوو او د دوی اړوند ارزښتونه به زموږ د ځواب لیست کې له نقشه څخه ذخیره کړو.

د بل لوی عنصر I لیټکوډ حل لپاره پلي کول

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 لیټکوډ حل لپاره د پیچلو تحلیل

د وخت پیچلتیا

O (m + n): لومړی ، موږ د لیست 2 تعقیب کوو ترڅو د لیست 2 ټولو عناصرو لپاره راتلونکي لوی عنصر ومومئ. بیا ، موږ د ځواب ضمیمه کولو لپاره لیست 1 تعقیب کوو. نو ، د وخت پیچلتیا د دواړه لیست اوږدوالي مجموعه ده.

د ځای پیچلتیا 

O (n): موږ د O (1) وخت کې هر کلي ته د ځواب موندلو لپاره نقشه کاروو ، پدې توګه د ځای پیچلتیا O (n) ده.