Замените елементе највећим елементом на десној страни решењем са кодом


Ниво тешкоће Лако
Често питани у амазонка
Ред

Проблем Замените елементе највећим елементом на десној страни решењем Леетцоде пружа нам поредак или вектор целих бројева. Проблем је тражио да све елементе заменимо елементом који је највећи међу свим елементима на десној страни. Па размислите да ли смо имали низ или секвенцу, {а, б, ц}. Ако бројеви прате тренд, б> ц> а. Дакле, према питању, излаз треба да буде {б, ц, -1}. Пре него што заронимо дубоко у решење, проверимо неколико примера.

Замените елементе највећим елементом на десној страни решењем са кодом

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

Објашњење: Излаз је лако разумљив, јер је сваки елемент замењен највећим елементом десно од њега.

[400]
[-1]

Објашњење: Будући да нема елемента десно од тренутног броја. Тако враћамо -1 као излаз.

Приступ за замену елемената највећим елементом на десној страни решењем Леетцоде

Проблем јасно наводи сам назив. Проблем каже да се сваки елемент замењује највећим елементом који се јавља на његовој десној страни. Сада остаје само да се симулира процес. То можемо лако учинити ако започнемо прелазак низа с десне стране. Дакле, уместо да идемо са леве стране, почињемо са десне стране. Задржавамо елемент који чува максимум пронађеног елемента до сада. Тренутни елемент чувамо у променљивој, а затим настављамо да ажурирамо максималну вредност. У овом тренутку можемо заменити тренутни елемент са највећим елементом / максималним елементом.

Код за замену елемената са највећим елементом на десној страни решењем Леетцоде

Ц ++ код

#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

Анализа сложености

Временска сложеност

НА), пошто једном прелазимо низ. Сложеност времена је такође линеарна.

Сложеност простора

О (1), алгоритам је на месту и стога је сложеност простора константна.