अगला ग्रेटर एलिमेंट I Leetcode Solution


कठिनाई स्तर आसान
में अक्सर पूछा वीरांगना ब्लूमबर्ग
धुआँरा

समस्या का विवरण

इस समस्या में, हमें दो सूचियाँ दी गई हैं, जिसमें पहली सूची दूसरी सूची के सबसेट है। पहली सूची के प्रत्येक तत्व के लिए, हमें दूसरी सूची में अगले अधिक तत्व का पता लगाना होगा।

अगला ग्रेटर एलिमेंट I Leetcode Solution

उदाहरण

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 के प्रत्येक तत्व को पहले list2 में खोजा जाता है, उसके बाद इसके अगले अधिक तत्व को खोजा जाता है। हम एक ध्वज चर का उपयोग करके ऐसा कर रहे हैं। सूची 1 के प्रत्येक तत्व के लिए, इसे पहले गलत पर सेट किया जाता है। जब हमने सूची 2 में तत्व पाया है, तो यह सही पर सेट है। उसके बाद, जब हम अगली बड़ी खोज करेंगे, हम इसे फिर से झूठे पर सेट करेंगे। ऐसा करने पर, हमें पता चलेगा कि उस चर के लिए 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 Leetcode समाधान के लिए जटिलता विश्लेषण

समय जटिलता

ओ (एम * एन): संख्या 1 के प्रत्येक तत्व के लिए हम अंक 2 से दाएं से रैखिक रूप से ट्रेस कर रहे हैं। इस प्रकार, समय जटिलता O (m * n) है जहां m और n सूचियों की लंबाई है।

अंतरिक्ष जटिलता 

ओ (1): कोई अतिरिक्त स्थान का उपयोग नहीं किया गया (ans array के लिए प्रयुक्त स्थान इसलिए नहीं माना जाता क्योंकि यह आवश्यक है)।

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

इस दृष्टिकोण में दो भाग शामिल हैं।
सबसे पहले, हम रैखिक समय में list2 के प्रत्येक तत्व के अगले बड़े तत्व को प्राप्त करने के लिए एक स्टैक का उपयोग कर रहे हैं। प्रत्येक तत्व का अगला बड़ा तत्व एक में संग्रहीत किया जाता है नक्शा.
दूसरे, हम मानचित्र का उपयोग करके हमारे उत्तर सरणी में list1 के प्रत्येक तत्व के लिए उत्तर संग्रहीत करेंगे।

तो, हम सूची 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 Leetcode समाधान के लिए जटिलता विश्लेषण

समय जटिलता

ओ (एम + एन): सबसे पहले, हम list2 के सभी तत्वों के लिए अगले अधिक से अधिक तत्व खोजने के लिए list2 का पता लगा रहे हैं। फिर, हम उत्तरों को संलग्न करने के लिए list1 का पता लगा रहे हैं। तो, समय जटिलता दोनों सूचियों की लंबाई का योग है।

अंतरिक्ष जटिलता 

पर): हम O (1) समय में किसी भी कुंजी का उत्तर खोजने के लिए एक मानचित्र का उपयोग कर रहे हैं, इस प्रकार अंतरिक्ष जटिलता O (n) है।