Elementləri sağ tərəfdəki lekod həllində ən yaxşı elementlə əvəz edin

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

Elementləri Sağ Tərəfdəki Leetcode Həllində Ən Böyük Elementlə Əvəz Et problemi bizə array və ya tam ədəd vektoru. Problem, bütün elementləri sağ tərəfdəki bütün elementlər arasında ən böyük olan elementlə əvəz etməyimizi istədi. Buna görə bir sıra və ya ardıcıllığımız olub olmadığını düşünün, {a, b, c}. Əgər rəqəmlər trendə uyğun gəlirsə, b> c> a. Beləliklə, suala uyğun olaraq, çıxış {b, c, -1} olmalıdır. Çözümün dərinliyinə dalmadan əvvəl, bir neçə nümunəni nəzərdən keçirək.

Elementləri sağ tərəfdəki lekod həllində ən yaxşı elementlə əvəz edinPin

[17,18,5,4,6,1]
[18,6,6,6,1,-1]

İzahat: Çıxışı anlamaq asandır, çünki hər element onun sağındakı ən böyük elementlə əvəz edilmişdir.

[400]
[-1]

İzahat: Cari rəqəmin sağında bir element olmadığı üçün. Beləliklə, çıxışı olaraq -1-i qaytarırıq.

Sağ Leetcode Həllində Elementləri Ən Böyük Elementlə Əvəz Etmə yanaşması

Problem problemi öz adı ilə açıq şəkildə ifadə edir. Problem hər bir elementin sağ tərəfində baş verən ən böyük elementlə əvəz edilməsini tələb edir. İndi yalnız prosesi simulyasiya etmək qalır. Dizini sağ tərəfdən keçməyə başlasaq, bunu asanlıqla edə bilərik. Beləliklə, sol tərəfdən getmək əvəzinə sağ tərəfdən başlayırıq. İndiyə qədər tapılan maksimum elementi saxlayan bir element saxlayırıq. Mövcud elementi dəyişəndə ​​saxlayırıq, sonra maksimum dəyəri yeniləməyə davam edirik. Bu nöqtədə, cari elementi ən böyük element / maksimum element ilə əvəz edə bilərik.

Elementləri Sağ tərəfdəki Leccode həllində ən böyük elementlə əvəz etmək üçün kod

C ++ kodu

#include <bits/stdc++.h>
using namespace std;

vector<int> replaceElements(vector<int>& arr) {
    int mx = -1, a;
    int n = arr.size();
    for (int i = n - 1; i >= 0; --i) {
        a = arr[i];
        arr[i] = mx;
        mx = max(mx, a);
    }
    return arr;
}

int main(){
    vector<int> arr = {17,18,5,4,6,1};
    vector<int> output = replaceElements(arr);
    for(int i=0;i<6;i++)
        cout<<output[i]<<" ";
}
18 6 6 6 1 -1

Java kodu

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
  public static int[] replaceElements(int[] arr) {
        int mx = -1, a;
        int n = arr.length;
        for (int i = n - 1; i >= 0; --i) {
            a = arr[i];
            arr[i] = mx;
            mx = Math.max(mx, a);
        }
        return arr;
    }
    
  public static void main (String[] args) throws java.lang.Exception{
    int[] arr = {17,18,5,4,6,1};
    int[] output = replaceElements(arr);
    for(int i=0;i<6;i++)
      System.out.print(output[i]+" ");
  }
}
18 6 6 6 1 -1

Mürəkkəblik təhlili

Zaman mürəkkəbliyi

O (N), serialı bir dəfə keçdiyimiz üçün. Zamanın mürəkkəbliyi də doğrudur.

Kosmik Mürəkkəblik

O (1), alqoritm yerində olanıdır və beləliklə kosmik mürəkkəblik sabitdir.

Şərh yaz

Translate »
1