Sonrakı Böyük Element I Leetcode Həll

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Amazon Bloomberg
alqoritmlər kodlaşdırma müsahibə müsahibə hazırlığı LeetCode LeetCodeSolutions QalaqBaxılıb 31

Problem bəyanat

Bu problemdə bizə birinci siyahının ikinci siyahının alt dəsti olduğu iki siyahı verilir. Birinci siyahının hər bir elementi üçün ikinci siyahıda növbəti böyük elementi tapmalıyıq.

Sonrakı Böyük Element I Leetcode HəllPin

misal

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

Explanation:

list1-in birinci elementi üçün, yəni 4-də list2-də daha böyük element yoxdur, buna görə cavabı -1-dir.
list1-in ikinci elementi üçün, yəni 1-də siyahı 3-də 1-dən 2-ü böyükdür, buna görə cavabı 3-dür.
list1-in üçüncü elementi üçün, yəni 2 üçün list2-də daha böyük element yoxdur, buna görə cavabı -1-dir.

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

Yanaşma 1 (kobud güc)

Bu yanaşmada, list1 üçün hər bir element üçün növbəti böyük elementi loop2 üçün iç içə istifadə edərək listXNUMX-də xətti keçid edərək tapırıq.
List1-in hər bir elementi əvvəlcə list2-də axtarılır, sonra növbəti böyük elementi axtarılır. Bunu bayraq dəyişənindən istifadə edərək edirik. List1 hər elementi üçün əvvəlcə false olaraq təyin olunur. List2-də element tapdıqda, doğru olaraq ayarlanır. Bundan sonra növbəti böyüyünü tapdığımızda onu yenidən yalan vəziyyətinə gətirəcəyik. Bunu etməklə, list2-də bu dəyişən üçün növbəti daha böyük bir elementin olduğunu və ya birinin olmadığını biləcəyik.

  • Bayraq dəyişəni doğrudursa, deməli həmin element üçün daha böyük bir dəyər tapa bilmədik.
  • Əgər bayraq dəyişəni yanlışdırsa, deməli həmin element üçün növbəti daha böyük bir dəyər tapmışıq.

Beləliklə, hər bir daxili döngənin sonunda bayraq dəyərinə görə cavab olaraq -1 əlavə edəcəyik.

Next Greater Element I Leetcode Solution üçün tətbiqetmə

C ++ Proqramı

#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 Proqramı

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

Növbəti Böyük Element I Leetcode Həlli üçün Mürəkkəblik Analizi

Zamanın mürəkkəbliyi

O (m * n): Nums1-in hər bir elementi üçün nums2-ni soldan sağa xətti keçirik. Beləliklə, zamanın mürəkkəbliyi O (m * n) -dir, burada m və n - siyahıların uzunluğu.

Kosmik Mürəkkəblik 

O (1): Əlavə yer istifadə edilmir (ans array üçün istifadə edilmiş boşluq nəzərə alınmır, çünki bu zəruridir).

Yanaşma 2 (yığını istifadə etməklə)

Bu yanaşma iki hissədən ibarətdir.
Birincisi, line2 müddətində hər bir listXNUMX elementinin növbəti böyük elementini əldə etmək üçün bir yığından istifadə edirik. Hər bir elementin növbəti böyük elementi a-da saxlanılır xəritə.
İkincisi, siyahını hər elementi üçün cavabı xəritədən istifadə edərək cavab massivimizdə saxlayacağıq.

Beləliklə, list2-dən keçib cari saydan kiçik olan və eyni zamanda yığının üst hissəsindəki bütün elementləri dəfələrlə açacağıq, hər pop-da cari elementi hər açılan elementin ən yaxın cavabı olaraq qeyd edəcəyik. Bu Xəritəçəkmə üçün sadəcə bir xəritədən istifadə edəcəyik.
İndi yalnız bir sonrakı daha böyük elementləri ilə elementlərin bir Xəritəçəkmə olan bir xəritəmiz var.
Nəhayət, list1-i keçib cavab dəyərlərimizdə xəritədən müvafiq dəyərlərini saxlayacağıq.

Next Greater Element I Leetcode Solution üçün tətbiqetmə

C ++ Proqramı

#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 Proqramı

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

Növbəti Böyük Element I Leetcode Həlli üçün Mürəkkəblik Analizi

Zamanın mürəkkəbliyi

O (m + n): Birincisi, list2-nin bütün elementləri üçün növbəti böyük elementi tapmaq üçün list2-dən keçirik. Sonra cavabları əlavə etmək üçün list1-dən keçirik. Beləliklə, zamanın mürəkkəbliyi hər iki siyahının uzunluğunun cəmidir.

Kosmik Mürəkkəblik 

O (n): O (1) vaxtında istənilən düyməyə cavab tapmaq üçün xəritədən istifadə edirik, beləliklə kosmik mürəkkəblik O (n) -dir.

Şərh yaz

Translate »
1