Επόμενη λύση Greater Element I Leetcode  


Επίπεδο δυσκολίας Εύκολος
Συχνές ερωτήσεις αμαζόνα Bloomberg
αλγόριθμοι κωδικοποίησης συνέντευξη συνέντευξηprep LeetCode LeetCodeSolutions Στοίβα

Δήλωση προβλήματος  

Σε αυτό το πρόβλημα, μας δίνονται δύο λίστες στις οποίες η πρώτη λίστα είναι υποσύνολο της δεύτερης λίστας. Για κάθε στοιχείο της πρώτης λίστας, πρέπει να βρούμε το επόμενο μεγαλύτερο στοιχείο στη δεύτερη λίστα.

Επόμενη λύση 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 (Brute Force)  

Σε αυτήν την προσέγγιση, βρίσκουμε απλώς το επόμενο μεγαλύτερο στοιχείο για κάθε στοιχείο της λίστας1 κάνοντας γραμμική διέλευση στη λίστα2 χρησιμοποιώντας ένα ένθετο για βρόχο.
Κάθε στοιχείο της λίστας 1 πραγματοποιείται πρώτα αναζήτηση στη λίστα2, και στη συνέχεια αναζητείται το επόμενο μεγαλύτερο στοιχείο του. Το κάνουμε αυτό χρησιμοποιώντας μια μεταβλητή flag. Για κάθε στοιχείο της λίστας 1, ορίζεται πρώτα σε false. Όταν βρούμε το στοιχείο στη λίστα2, ορίζεται ως αληθινό. Μετά από αυτό, όταν θα βρούμε το επόμενο μεγαλύτερο, θα το θέσουμε ξανά σε ψευδές. Με αυτόν τον τρόπο, θα μάθουμε ότι υπάρχει οποιοδήποτε επόμενο μεγαλύτερο στοιχείο στη λίστα2 για αυτήν τη μεταβλητή ή ότι δεν υπάρχει.

  • Εάν η μεταβλητή flag είναι αληθής, αυτό σημαίνει ότι δεν θα μπορούσαμε να βρούμε καμία επόμενη μεγαλύτερη τιμή για αυτό το στοιχείο.
  • Εάν η μεταβλητή flag είναι ψευδής, αυτό σημαίνει ότι έχουμε βρει μια επόμενη μεγαλύτερη τιμή για αυτό το στοιχείο.
Βλέπε επίσης
Μέγιστη λύση 69 αριθμών Leetcode

Έτσι, στο τέλος κάθε εσωτερικού βρόχου, σύμφωνα με την τιμή της σημαίας θα εισάγουμε το -1 ως απάντηση.

Εφαρμογή για το Next Greater 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

Ανάλυση πολυπλοκότητας για το επόμενο Greater Element I Leetcode Solution

Χρόνος πολυπλοκότητας

O (m * n): Για κάθε στοιχείο των αριθμών1 διασχίζουμε τους αριθμούς2 γραμμικά από αριστερά προς τα δεξιά. Έτσι, η πολυπλοκότητα του χρόνου είναι O (m * n) όπου τα m και n είναι μήκος λιστών.

Διαστημική πολυπλοκότητα 

O (1): Δεν χρησιμοποιείται επιπλέον χώρος (το διάστημα που χρησιμοποιείται για πίνακα ans δεν λαμβάνεται υπόψη επειδή είναι απαραίτητο).

Προσέγγιση 2 (Χρήση στοίβας)  

Αυτή η προσέγγιση περιλαμβάνει δύο μέρη.
Πρώτον, χρησιμοποιούμε μια στοίβα για να πάρουμε το επόμενο μεγαλύτερο στοιχείο κάθε στοιχείου της λίστας2 σε γραμμικό χρόνο. Το επόμενο μεγαλύτερο στοιχείο κάθε στοιχείου αποθηκεύεται σε ένα χάρτη.
Δεύτερον, θα αποθηκεύσουμε την απάντηση για κάθε στοιχείο της λίστας1 στον πίνακα απαντήσεων χρησιμοποιώντας τον χάρτη.

Έτσι, θα διασχίσουμε τη λίστα2 και θα εμφανίσουμε επανειλημμένα όλα τα στοιχεία από την κορυφή της στοίβας που είναι μικρότερα από τον τρέχοντα αριθμό και ταυτόχρονα, σε κάθε ποπ θα καταγράψουμε το τρέχον στοιχείο ως την πλησιέστερη μεγαλύτερη απάντηση κάθε αναδυόμενου στοιχείου. Για αυτήν τη χαρτογράφηση, θα χρησιμοποιήσουμε απλά έναν χάρτη.
Τώρα, έχουμε έναν χάρτη που είναι απλώς μια χαρτογράφηση στοιχείων με τα αντίστοιχα επόμενα μεγαλύτερα στοιχεία τους.
Τέλος, θα διασχίσουμε τη λίστα1 και θα αποθηκεύσουμε τις αντίστοιχες τιμές τους από το χάρτη στη λίστα απαντήσεων.

Βλέπε επίσης
Αναζήτηση του Word

Εφαρμογή για το Next Greater 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

Ανάλυση πολυπλοκότητας για το επόμενο Greater Element I Leetcode Solution

Χρόνος πολυπλοκότητας

O (m + n): Πρώτον, διασχίζουμε τη λίστα2 για να βρούμε το επόμενο μεγαλύτερο στοιχείο για όλα τα στοιχεία της λίστας2. Στη συνέχεια, διασχίζουμε τη λίστα1 για να προσθέσουμε τις απαντήσεις. Έτσι, η πολυπλοκότητα του χρόνου είναι το άθροισμα των δύο λιστών.

Διαστημική πολυπλοκότητα 

Επί): Χρησιμοποιούμε έναν χάρτη για να βρούμε απάντηση σε οποιοδήποτε κλειδί στην ώρα O (1), επομένως η πολυπλοκότητα του διαστήματος είναι O (n).

1