Рубрики

Переставить массив в максимально минимальной форме | Комплект 1

Учитывая отсортированный массив натуральных чисел, переставьте массив поочередно, то есть первый элемент должен быть максимальным значением, вторым минимальным значением, третьей второй максимумом, четвертой секундой и так далее.

Примеры:

Input: arr[] = {1, 2, 3, 4, 5, 6, 7}
Output: arr[] = {7, 1, 6, 2, 5, 3, 4}

Input: arr[] = {1, 2, 3, 4, 5, 6}
Output: arr[] = {6, 1, 5, 2, 4, 3}

Ожидаемая сложность времени: O (n).

Идея состоит в том, чтобы использовать вспомогательный массив. Мы поддерживаем два указателя, один на крайний левый или наименьший элемент, а другой на крайний правый или наибольший элемент. Мы больше указываем друг на друга и копируем элементы этих указателей во вспомогательный массив. Наконец, мы копируем вспомогательный массив обратно в исходный массив.

Ниже приведен пробный запуск вышеуказанного подхода:

Ниже приведена реализация вышеуказанного подхода:

C ++

// C ++ программа для перестановки массива за минимум
// максимальная форма
#include <bits/stdc++.h>

using namespace std;

  
// Печатает max в первой позиции, min во второй позиции
// второй максимум на третьей позиции, второй мин на четвертой
// положение и так далее.

void rearrange(int arr[], int n)

{

    // Вспомогательный массив для хранения измененного массива

    int temp[n];

  

    // Индексы самых маленьких и самых больших элементов

    // из оставшегося массива.

    int small=0, large=n-1;

  

    // Чтобы указать, нужно ли нам копировать rmaining

    // наибольший или оставшийся наименьший на следующей позиции

    int flag = true;

  

    // Сохраняем результат в temp []

    for (int i=0; i<n; i++)

    {

        if (flag)

            temp[i] = arr[large--];

        else

            temp[i] = arr[small++];

  

        flag = !flag;

    }

  

    // Копируем temp [] в arr []

    for (int i=0; i<n; i++)

        arr[i] = temp[i];

}

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

int main()

{

    int arr[] = {1, 2, 3, 4, 5, 6};

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

  

    cout << "Original Arrayn";

    for (int i=0; i<n; i++)

        cout << arr[i] << " ";

  

    rearrange(arr, n);

  

    cout << "nModified Arrayn";

    for (int i=0; i<n; i++)

        cout << arr[i] << " ";

    return 0;

}

Джава

// Java программа для перестановки массива за минимум
// максимальная форма

  

import java.util.Arrays;

  

public class GFG

{

    // Печатает max в первой позиции, min во второй позиции

    // второй максимум на третьей позиции, второй мин на четвертой

    // положение и так далее.

    static void rearrange(int[] arr, int n)

    {

        // Вспомогательный массив для хранения измененного массива

        int temp[] = new int[n];

      

        // Индексы самых маленьких и самых больших элементов

        // из оставшегося массива.

        int small=0, large=n-1;

      

        // Чтобы указать, нужно ли нам копировать rmaining

        // наибольший или оставшийся наименьший на следующей позиции

        boolean flag = true;

      

        // Сохраняем результат в temp []

        for (int i=0; i<n; i++)

        {

            if (flag)

                temp[i] = arr[large--];

            else

                temp[i] = arr[small++];

      

            flag = !flag;

        }

      

        // Копируем temp [] в arr []

        arr = temp.clone();

    }

  

    // Метод драйвера для проверки вышеуказанной функции

    public static void main(String[] args) 

    {

        int arr[] = new int[]{1, 2, 3, 4, 5, 6};

          

        System.out.println("Original Array ");

        System.out.println(Arrays.toString(arr));

          

        rearrange(arr,arr.length);

          

        System.out.println("Modified Array ");

        System.out.println(Arrays.toString(arr));

      

    }

}

питон

# Python программа для перестановки массива за минимум
# максимальная форма

  
# Печатает max на первой позиции, min на второй позиции
# второй максимум на третьей позиции, второй мин на четвертой
# положение и так далее.

def rearrange(arr, n):

    # Вспомогательный массив для хранения измененного массива

    temp = n*[None]

  

    # Индексы самых маленьких и самых больших элементов

    # из оставшегося массива.

    small,large =0,n-1

  

    # Чтобы указать, нужно ли нам копировать rmaining

    # наибольший или оставшийся наименьший на следующей позиции

    flag = True

  

    # Сохранить результат в temp []

    for i in range(n):

        if flag is True:

            temp[i] = arr[large]

            large -= 1

        else:

            temp[i] = arr[small]

            small += 1

  

        flag = bool(1-flag)

  

    # Скопировать temp [] в arr []

    for i in range(n):

        arr[i] = temp[i]

    return arr

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

arr = [1, 2, 3, 4, 5, 6]

n = len(arr)

print("Original Array")

print(arr)

print("Modified Array")

print(rearrange(arr, n))

  
# Этот код предоставлен Pratik Chhajer

C #

// C # программа для перестановки
// массив минимум
// максимальная форма

using System;

  

class GFG

{

  
// Печатает макс на первой позиции,
// мин на второй позиции второй
// максимум на третьей позиции, второй
// мин на четвертой позиции и так далее.

static void rearrage(int[] arr, 

                     int n)

{

    // Вспомогательный массив для

    // держать измененный массив

    int []temp = new int[n];

  

    // Индексы самых маленьких

    // и самые большие элементы

    // из оставшегося массива.

    int small = 0, large = n - 1;

  

    // Чтобы указать, что мы

    // нужно скопировать rmaining

    // самый большой или оставшийся

    // наименьший на следующей позиции

    bool flag = true;

  

    // Сохраняем результат в temp []

    for (int i = 0; i < n; i++)

    {

        if (flag)

            temp[i] = arr[large--];

        else

            temp[i] = arr[small++];

  

        flag = !flag;

    }

  

    // Копируем temp [] в arr []

    for (int i = 0; i < n; i++)

        arr[i] = temp[i];

}

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

static void Main()

{

    int[] arr = {1, 2, 3, 4, 

                 5, 6};

  

    Console.WriteLine("Original Array");

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

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

  

    rearrage(arr, arr.Length);     

  

    Console.WriteLine("\nModified Array");

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

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

}
}

  
// Этот код добавлен
// Sam007

PHP

<?php
// PHP программа для перестановки массива в
// форма минимума-максимума

  
// Печатает max в первой позиции, min в
// вторая позиция вторая максимальная третья
// позиция, вторая минута на четвертой
// положение и так далее.

function rearrange(&$arr, $n)

{

    // Вспомогательный массив для хранения измененного массива

    $temp = array();

  

    // Индексы самых маленьких и самых больших элементов

    // из оставшегося массива.

    $small = 0;

    $large = $n - 1;

  

    // Чтобы указать, нужно ли нам копировать

    // оставаясь самым большим или оставаясь самым маленьким

    // на следующей позиции

    $flag = true;

  

    // Сохраняем результат в temp []

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

    {

        if ($flag)

            $temp[$i] = $arr[$large--];

        else

            $temp[$i] = $arr[$small++];

  

        $flag = !$flag;

    }

  

    // Копируем temp [] в arr []

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

        $arr[$i] = $temp[$i];

}

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

$arr = array(1, 2, 3, 4, 5, 6);

$n = count($arr);

  

echo "Original Arrayn\n";

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

    echo $arr[$i] . " ";

  

rearrange($arr, $n);

  

echo "\nModified Arrayn\n";

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

    echo $arr[$i] . " ";

      
// Этот код предоставлен
// Раджпут-Джи
?>


Выход:

Original Array
1 2 3 4 5 6
Modified Array
6 1 5 2 4 3 

Сложность времени: O (n)
Вспомогательное пространство: O (n)

Упражнение: Как решить эту проблему, если дополнительное пространство не разрешено?

Переставить массив в максимально минимальной форме | Набор 2 (O (1) дополнительное пространство)

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

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

Переставить массив в максимально минимальной форме | Комплект 1

0.00 (0%) 0 votes