अर्को ग्रेटर एलिमेन्ट I लीटकोड समाधान


कठिनाई तह सजिलो
बारम्बार सोधिन्छ अमेजन ब्लूमबर्ग
थाक

समस्या वक्तव्य

यस समस्यामा, हामीलाई दुई सूचीहरू दिइन्छ जसमा पहिलो सूची दोस्रो सूचीको सबसेट हो। पहिलो सूचीको प्रत्येक तत्वका लागि, हामीले दोस्रो सूचीमा अर्को ठूलो तत्त्व पत्ता लगाउनु पर्छ।

अर्को ग्रेटर एलिमेन्ट I लीटकोड समाधान

उदाहरणका

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

व्याख्या:

list1 को पहिलो तत्त्वका लागि ie 4 को लागी list2 मा अर्को ठूलो कुनै तत्व छैन, त्यसैले यसको उत्तर -1 हो।
list1 को दोस्रो तत्वको लागि जस्तै १ को लागी सूची २ मा १ भन्दा than ठूलो छ, यसैले यसको उत्तर is हो।
list1 को तेस्रो एलिमेन्टको लागि उदाहरण २ को लागी list2 मा अर्को ठूलो एलिमेन्ट हुँदैन, त्यसैले यसको उत्तर -१ हो।

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

दृष्टिकोण १ (ब्रुट फोर्स)

यस दृष्टिकोणमा, हामी मात्र सूची १ को प्रत्येक एलिमेन्टको लागि अर्को ठूलो एलिमेन्ट फेला पार्दछौं सूची २ मा रेखीय ट्रैभर्सल गरेर लूपको लागि नेस्टेड प्रयोग गरेर।
List1 को प्रत्येक तत्व पहिले list2 मा खोजी गरिन्छ, त्यसपछि पछि यसको अर्को ठूलो तत्त्व खोजी हुन्छ। हामी फ्ल्याग भ्यारीएबलको प्रयोग गरेर यो गरिरहेका छौं। सूची 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 लीटकोड समाधानको लागि जटिलता विश्लेषण

समय जटिलता

O (m * n): Nums1 को प्रत्येक तत्व को लागी हामी nums2 लाई लाइन बाट बायाँ दायाँ बाट हिड्दै छौं। यसैले, समय जटिलता O (m * n) हो जहाँ m र n सूचीहरूको लम्बाई हो।

ठाउँ जटिलता 

O (१): कुनै अतिरिक्त स्थान प्रयोग गरिएको छैन (एर्रे एर्रेको लागि प्रयोग गरिएको स्पेसलाई मानिदैन किनकि त्यो आवश्यक छ)।

दृष्टिकोण २ (स्ट्याकको प्रयोग गरेर)

यस दृष्टिकोणमा दुई भागहरू छन्।
सबैभन्दा पहिले, हामी रैखिक समयमा list2 को प्रत्येक तत्वको अर्को ठूलो तत्व प्राप्त गर्न स्ट्याक प्रयोग गर्दैछौं। प्रत्येक तत्वको अर्को ठूलो तत्व a मा भण्डारण हुन्छ नक्सा.
दोस्रो, हामी लिस्ट १ को प्रत्येक एलिमेन्टको लागि उत्तर एरेमा नक्सा प्रयोग गरेर भण्डार गर्नेछौं।

त्यसो भए, हामी लिस्ट २ लाई ट्र्यावर्स गर्नेछौं र स्ट्याकको शीर्षबाट सबै एलिमेन्टहरू बारम्बार पप गर्नेछौं जुन हालको संख्या भन्दा सानो छ र एकै साथ प्रत्येक पपमा हामी प्रत्येक तत्वमा नजिकैको ठूलो जवाफको रूपमा वर्तमान एलिमेन्ट रेकर्ड गर्नेछौं। यस म्यापि .को लागि, हामी केवल नक्सा प्रयोग गर्नेछौं।
अब, हामीसँग नक्सा छ जुन केवल सम्बन्धित अर्को ठूलो तत्त्वहरूको एलिमेन्टहरूको म्यापि .्ग हो।
अन्तमा, हामी सूची १ लाई ट्रान्सवर्स गर्नेछौं र हाम्रो उत्तर सूचीमा नक्साबाट उनीहरूका सम्बन्धित मानहरू भण्डार गर्नेछौं।

अर्को ग्रेटर एलिमेन्ट 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): सर्वप्रथम, हामी list2 को सबै तत्वहरूको लागि अर्को ठूलो तत्व फेला पार्न list2 लाई ट्र्याभिंग गर्दैछौं। त्यसो भए, हामी उत्तरहरू जोड्न सूची १ ट्र्याभर्स गर्दैछौं। त्यसो भए, समय जटिलता दुबै सूचिहरूको लम्बाईको योग हो।

ठाउँ जटिलता 

O (n): हामी नक्शा प्रयोग गर्दैछौं O (१) समयमा कुनै कुञ्जीमा उत्तर खोज्न, यसैले अन्तरिक्ष जटिलता ओ (एन) हो।