შეცვალეთ ელემენტები უდიდესი ელემენტით მარჯვენა მხრიდან Leetcode ამონახსნით


Რთული ტური Easy
ხშირად ეკითხებიან Amazon
Array

პრობლემა შეცვალეთ ელემენტები უდიდესი ელემენტებით მარჯვენა მხარეს Leetcode Solution გვაძლევს მასივი ან მთელი რიცხვების ვექტორი. პრობლემამ მოგვმართა ყველა ელემენტის ჩანაცვლება ელემენტებით, რომელიც უდიდესია ყველა ელემენტის მარჯვენა მხარეს. გაითვალისწინეთ, გვქონდა თუ არა მასივი ან თანმიმდევრობა, {a, b, c}. თუ ციფრები მიჰყვება ტენდენციას, b> c> a. ამ კითხვის მიხედვით, გამომავალი უნდა იყოს {b, c, -1}. სანამ ხსნარში ღრმად ჩავუღრმავდებით, მოდით გადავამოწმოთ რამდენიმე მაგალითი.

შეცვალეთ ელემენტები უდიდესი ელემენტით მარჯვენა მხრიდან Leetcode ამონახსნით

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

განმარტება: გამომავალი გასაგებია, რადგან თითოეული ელემენტი შეიცვალა უდიდესი ელემენტით მის მარჯვნივ.

[400]
[-1]

განმარტება: რადგან მიმდინარე რიცხვის მარჯვნივ არ არის ელემენტი. ამრიგად, ჩვენ ვბრუნდებით -1-ს, როგორც გამომავალს.

მიდგომა უდიდესი ელემენტის ჩანაცვლებისადმი მარჯვენა მხარეს Leetcode ამოხსნისთვის

პრობლემა აშკარად ასახავს პრობლემას თავისი სახელით. პრობლემა ამბობს, რომ შეცვალოს თითოეული ელემენტი უდიდესი ელემენტით, რომელიც ხდება მის მარჯვენა მხარეს. ახლა მხოლოდ პროცესის სიმულაცია რჩება. ამის გაკეთება მარტივად შეგვიძლია, თუ დავიწყებთ მასივის გადახედვას მარჯვენა მხრიდან. ასე რომ, მარცხენა მხრიდან გადასვლის ნაცვლად, მარჯვენა მხრიდან ვიწყებთ. ჩვენ ვინახავთ ელემენტს, რომელიც ინახავს აქამდე აღმოჩენილ მაქსიმალურ ელემენტს. ჩვენ მიმდინარე ელემენტს ვინახავთ ცვლადში, შემდეგ ვაგრძელებთ მაქსიმალური მნიშვნელობის განახლებას. ამ ეტაპზე, ჩვენ შეგვიძლია შეცვალოთ ამჟამინდელი ელემენტი უდიდესი ელემენტით / მაქსიმალური ელემენტით.

კოდი, რათა შეცვალოთ ელემენტები უდიდესი ელემენტით მარჯვენა მხრიდან Leetcode ამოხსნაზე

C ++ კოდი

#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

ჯავის კოდი

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

სირთულის ანალიზი

დროის სირთულე

O (N), მას შემდეგ, რაც მასივს ერთხელ გადავკვეთთ. დროის სირთულე ასევე ხაზოვანია.

სივრცის სირთულე

O (1), ალგორითმი ადგილზეა და ამით სივრცის სირთულე მუდმივია.