Рубрики

Замените каждый элемент с наибольшим элементом на правой стороне

Учитывая массив целых чисел, замените каждый элемент следующим самым большим элементом (самым большим элементом справа) в массиве. Поскольку рядом с последним элементом нет элемента, замените его на -1. Например, если массив равен {16, 17, 4, 3, 5, 2}, его следует изменить на {17, 5, 5, 5, 2, -1}.

Мы настоятельно рекомендуем вам нажать здесь и попрактиковаться, прежде чем переходить к решению.

Вопрос очень похож на этот пост и решения тоже похожи.

Наивным методом является запуск двух циклов. Внешний цикл будет один за другим выбирать элементы массива слева направо. Внутренний цикл найдет самый большой элемент, присутствующий после выбранного элемента. Наконец, внешний цикл заменит выбранный элемент самым большим элементом, найденным внутренним циклом. Временная сложность этого метода будет O (n * n).
Сложный метод заключается в замене всех элементов с использованием одного обхода массива. Идея состоит в том, чтобы начать с самого правого элемента, перейти к левой стороне один за другим и отслеживать максимальный элемент. Замените каждый элемент максимальным элементом.

C ++

// C ++ Программа для замены каждого элемента с наибольшим
// элемент на правой стороне
#include <bits/stdc++.h>

using namespace std;

  
/ * Функция для замены каждого элемента на
следующий величайший элемент * /

void nextGreatest(int arr[], int size) 

      

    // Инициализируем следующий наибольший элемент

    int max_from_right = arr[size-1]; 

      

    // Следующий наибольший элемент для самого правого элемента

    // всегда -1

    arr[size-1] = -1; 

      

    // Заменить все остальные элементы следующим большим

    for(int i = size-2; i >= 0; i--) 

    

        // Сохраняем текущий элемент (понадобится позже для обновления

        // следующий величайший элемент)

        int temp = arr[i]; 

      

        // Заменить текущий элемент следующим наибольшим

        arr[i] = max_from_right; 

      

        // Обновляем самый большой элемент, если это необходимо

        if(max_from_right < temp) 

        max_from_right = temp; 

    

  
/ * Вспомогательная функция, которая печатает массив * /

void printArray(int arr[], int size) 

    int i; 

    for (i = 0; i < size; i++) 

        cout << arr[i] << " "

    cout << endl; 

  
/ * Программа драйвера для проверки вышеуказанной функции * /

int main() 

    int arr[] = {16, 17, 4, 3, 5, 2}; 

    int size = sizeof(arr)/sizeof(arr[0]); 

    nextGreatest (arr, size); 

    cout << "The modified array is: \n"

    printArray (arr, size); 

    return (0); 

  
// Это код, предоставленный rathbhupendra

С

// C Программа для замены каждого элемента с наибольшим
// элемент на правой стороне
#include <stdio.h>

  
/ * Функция для замены каждого элемента на

   следующий величайший элемент * /

void nextGreatest(int arr[], int size)

{

  // Инициализируем следующий наибольший элемент

  int max_from_right =  arr[size-1];

  

  // Следующий наибольший элемент для самого правого элемента

  // всегда -1

  arr[size-1] = -1;

  

  // Заменить все остальные элементы следующим большим

  for(int i = size-2; i >= 0; i--)

  {

    // Сохраняем текущий элемент (понадобится позже для обновления

    // следующий величайший элемент)

    int temp = arr[i];

  

    // Заменить текущий элемент следующим наибольшим

    arr[i] = max_from_right;

  

    // Обновляем самый большой элемент, если это необходимо

    if(max_from_right < temp)

       max_from_right = temp;

  }

}

  
/ * Вспомогательная функция, которая печатает массив * /

void printArray(int arr[], int size)

{

  int i;

  for (i=0; i < size; i++)

    printf("%d ", arr[i]);

  printf("\n");

}

  
/ * Программа драйвера для проверки вышеуказанной функции * /

int main()

{

  int arr[] = {16, 17, 4, 3, 5, 2};

  int size = sizeof(arr)/sizeof(arr[0]);

  nextGreatest (arr, size);

  printf ("The modified array is: \n");

  printArray (arr, size);

  return (0);

}

Джава

// Java-программа для замены каждого элемента
// самый большой элемент на правой стороне

import java.io.*;

  

class NextGreatest 

{

    / * Функция для замены каждого элемента на

       следующий величайший элемент * /

    static void nextGreatest(int arr[])

    {

        int size = arr.length;

  

        // Инициализируем следующий наибольший элемент

        int max_from_right =  arr[size-1];

  

        // Следующий наибольший элемент для самого правого

        // элемент всегда -1

        arr[size-1] = -1;

  

        // Заменить все остальные элементы следующим большим

        for (int i = size-2; i >= 0; i--)

        {

            // Сохраняем текущий элемент (нужен позже для

            // обновляем следующий элемент

            int temp = arr[i];

  

            // Заменить текущий элемент следующим наибольшим

            arr[i] = max_from_right;

  

            // Обновляем самый большой элемент, если это необходимо

            if(max_from_right < temp)

            max_from_right = temp;

        }

    }

  

    / * Вспомогательная функция, которая печатает массив * /

    static void printArray(int arr[])

    {

        for (int i=0; i < arr.length; i++)

        System.out.print(arr[i]+" ");

    }

  

    public static void main (String[] args)

    {

        int arr[] = {16, 17, 4, 3, 5, 2};

        nextGreatest (arr);

        System.out.println("The modified array:");

        printArray (arr);

    }

}
/ * Этот код предоставлен Девешом Агравалом * /

питон

# Программа Python для замены каждого элемента на
# величайший элемент на правой стороне

  
# Функция для замены каждого элемента следующим большим
# элемент

def nextGreatest(arr):

  

    size = len(arr)

  

    # Инициализировать следующий элемент

    max_from_right = arr[size-1]

  

    # Следующий наибольший элемент для самого правого элемента

    # всегда -1

    arr[size-1] = -1

  

    # Заменить все остальные элементы следующим большим

    for i in range(size-2,-1,-1):

  

        # Сохранить текущий элемент (требуется позже для обновления

        # следующий величайший элемент)

        temp = arr[i]

  

        # Заменить текущий элемент следующим большим

        arr[i]=max_from_right

  

        # Обновите лучший элемент, если это необходимо

        if max_from_right< temp:

            max_from_right=temp

  
# Сервисная функция для печати массива

def printArray(arr):

    for i in range(0,len(arr)):

        print arr[i],

  
# Функция драйвера для проверки вышеуказанной функции

arr = [16, 17, 4, 3, 5, 2]

nextGreatest(arr)

print "Modified array is"

printArray(arr)
# Этот код предоставлен Девешом Агравалом

C #

// C # Программа для замены каждого элемента на
// самый большой элемент на правой стороне

using System;

  

class GFG {

      

    / * Функция для замены каждого элемента

    следующий величайший элемент * /

    static void nextGreatest(int []arr)

    {

        int size = arr.Length;

  

        // Инициализируем следующий наибольший элемент

        int max_from_right = arr[size-1];

  

        // Следующий величайший элемент для

        // самый правый элемент всегда -1

        arr[size-1] = -1;

  

        // Заменить все остальные элементы на

        // следующий наибольший

        for (int i = size-2; i >= 0; i--)

        {

            // Сохраняем текущий элемент (необходим

            // позже для обновления следующего

            // величайший элемент)

            int temp = arr[i];

  

            // Заменить текущий элемент на

            // следующий величайший

            arr[i] = max_from_right;

  

            // Обновить самый большой элемент, если

            // нужен

            if(max_from_right < temp)

            max_from_right = temp;

        }

    }

  

    / * Вспомогательная функция, которая печатает массив * /

    static void printArray(int []arr)

    {

        for (int i=0; i < arr.Length; i++)

        Console.Write(arr[i]+" ");

    }

  

    public static void Main ()

    {

        int []arr = {16, 17, 4, 3, 5, 2};

        nextGreatest (arr);

        Console.WriteLine("The modified array:");

        printArray (arr);

    }

}

  
/ * Этот код предоставлен vt_m. * /

PHP

<?php
// PHP программа для замены каждого элемента
// самый большой элемент на правой стороне

  
/ * Функция для замены каждого элемента
со следующим самым большим элементом * /

function nextGreatest(&$arr, $size

    // Инициализируем следующий наибольший элемент

    $max_from_right = $arr[$size - 1]; 

      

    // Следующий величайший элемент для

    // самый правый элемент всегда -1

    $arr[$size - 1] = -1; 

      

    // Заменить все остальные элементы на

    // следующий величайший

    for($i = $size - 2; $i >= 0; $i--) 

    

        // Сохраняем текущий элемент (необходим

        // позже для обновления следующего

        // величайший элемент)

        $temp = $arr[$i]; 

      

        // Заменить текущий элемент на

        // следующий наибольший

        $arr[$i] = $max_from_right

      

        // Обновить самый большой элемент,

        // если нужно

        if($max_from_right < $temp

        $max_from_right = $temp

    

  
// Вспомогательная функция, которая печатает массив

function printArray($arr, $size

    for ($i = 0; $i < $size; $i++) 

        echo $arr[$i] . " "

    echo "\n"

  
// Код драйвера

$arr = array(16, 17, 4, 3, 5, 2); 

$size = count($arr); 

nextGreatest ($arr, $size); 

echo "The modified array is: \n"

printArray ($arr, $size); 

  
// Этот код предоставлен
// ратбхупендра
?>


Выход:

The modified array is:
17 5 5 5 2 -1

Сложность времени: O (n), где n — количество элементов в массиве.

Пожалуйста, пишите комментарии, если вы обнаружите, что какой-либо из приведенных выше кодов / алгоритмов неверен, или найдете другие способы решения той же проблемы.

Рекомендуемые посты:

Замените каждый элемент с наибольшим элементом на правой стороне

0.00 (0%) 0 votes