Рубрики

Переупорядочить массив так, чтобы четные элементы индекса были меньше, а нечетные элементы индекса больше

Для данного массива переставьте массив так, чтобы:

  1. Если индекс i четный, arr [i] <= arr [i + 1]
  2. Если индекс i нечетный, arr [i]> = arr [i + 1]

Примечание: может быть несколько ответов.

Примеры:

Input  : arr[] = {2, 3, 4, 5} 
Output : arr[] = {2, 4, 3, 5}
Explanation : Elements at even indexes are
smaller and elements at odd indexes are greater
than their next elements

Note : Another valid answer
is arr[] = {3, 4, 2, 5}

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

Эта проблема похожа на сортировку массива в форме волны .

Простое решение — отсортировать массив в порядке убывания, а затем, начиная со второго элемента, поменять местами соседние элементы.

Эффективное решение состоит в том, чтобы перебрать массив и поменять местами элементы в соответствии с заданным условием.
Если у нас есть массив длины n, то мы выполняем итерацию от индекса 0 до n-2 и проверяем заданное условие.
В любой момент времени, если i чётно и arr [i]> arr [i + 1], мы меняем местами arr [i] и arr [i + 1]. Точно так же, если я нечетный и
arr [i] <arr [i + 1], затем мы меняем местами arr [i] и arr [i + 1].

Для данного примера:
Перед перестановкой arr [] = {2, 3, 4, 5}
Начните итерацию по массиву до индекса 2 (при n = 4)

First Step:
At i = 0, arr[i] = 2 and arr[i+1] = 3. As i is even and arr[i] < arr[i+1], don’t need to swap.
Second step:
At i = 1, arr[i] = 3 and arr[i+1] = 4. As i is odd and arr[i] < arr[i+1], swap them.
Now arr[] = {2, 4, 3, 5}
Third step:
At i = 2, arr[i] = 3 and arr[i+1] = 5. So, don’t need to swap them

После перестановки arr [] = {2, 4, 3, 5}

C ++

// код CPP для перестановки массива таким образом, чтобы
// четные элементы индекса меньше и нечетны
// элементы индекса больше, чем их
// следующий.
#include <iostream>

using namespace std;

  

void rearrange(int* arr, int n)

{

    for (int i = 0; i < n - 1; i++) {

        if (i % 2 == 0 && arr[i] > arr[i + 1])

            swap(arr[i], arr[i + 1]);

  

        if (i % 2 != 0 && arr[i] < arr[i + 1])

            swap(arr[i], arr[i + 1]);

    }

}

  
/ * Утилита, которая печатает массив в

   линия * /

void printArray(int arr[], int size)

{

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

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

  

    cout << endl;

}

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

int main()

{

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

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

  

    cout << "Before rearranging: \n";

    printArray(arr, n);

  

    rearrange(arr, n);

  

    cout << "After rearranging: \n";

    printArray(arr, n);

  

    return 0;

}

Джава

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

  

class GFG {

  

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

    {

  

        int temp;

        for (int i = 0; i < n - 1; i++) {

            if (i % 2 == 0 && arr[i] > arr[i + 1]) {

                temp = arr[i];

                arr[i] = arr[i + 1];

                arr[i + 1] = temp;

            }

            if (i % 2 != 0 && arr[i] < arr[i + 1]) {

                temp = arr[i];

                arr[i] = arr[i + 1];

                arr[i + 1] = temp;

            }

        }

    }

  

    / * Утилита, которая печатает массив в

    линия * /

    static void printArray(int arr[], int size)

    {

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

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

  

        System.out.println();

    }

  

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

    public static void main(String[] args)

    {

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

        int n = arr.length;

  

        System.out.print("Before rearranging: \n");

        printArray(arr, n);

  

        rearrange(arr, n);

  

        System.out.print("After rearranging: \n");

        printArray(arr, n);

    }

}

  
// Этот код предоставлен Anant Agarwal.

python3

# Python код для перестановки
# массив такой, что
# четные элементы индекса
# меньше и нечетны
# элементы индекса
# больше, чем их
# следующий.

  

def rearrange(arr, n):

  

    for i in range(n - 1):

        if (i % 2 == 0 and arr[i] > arr[i + 1]):

          

            temp = arr[i]

            arr[i]= arr[i + 1]

            arr[i + 1]= temp

          

        if (i % 2 != 0 and arr[i] < arr[i + 1]):

           

            temp = arr[i]

            arr[i]= arr[i + 1]

            arr[i + 1]= temp

             

   
# Утилита, которая печатает массив в
# строка

def printArray(arr, size):

  

    for i in range(size):

        print(arr[i], " ", end ="")

   

    print()

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

  

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

n = len(arr)

   

print("Before rearranging: ")

printArray(arr, n)

   
rearrange(arr, n)

   

print("After rearranging:")

printArray(arr, n);

  
# Этот код добавлен
# Анант Агарвал.

C #

// код C # для перестановки массива такой
// что даже элементы индекса меньше
// и нечетные элементы индекса больше
// чем их дальше.

using System;

  

class GFG {

  

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

    {

        int temp;

        for (int i = 0; i < n - 1; i++) {

            if (i % 2 == 0 && arr[i] > arr[i + 1])

            {

                temp = arr[i];

                arr[i] = arr[i + 1];

                arr[i + 1] = temp;

            }

              

            if (i % 2 != 0 && arr[i] < arr[i + 1])

            {

                temp = arr[i];

                arr[i] = arr[i + 1];

                arr[i + 1] = temp;

            }

        }

    }

  

    / * Утилита, которая печатает массив в

    линия * /

    static void printArray(int[] arr, int size)

    {

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

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

  

        Console.WriteLine();

    }

  

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

    public static void Main()

    {

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

        int n = arr.Length;

  

        Console.WriteLine("Before rearranging: ");

        printArray(arr, n);

  

        rearrange(arr, n);

  

        Console.WriteLine("After rearranging: ");

        printArray(arr, n);

    }

}

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

PHP

<?php 
// PHP-код для перестановки массива такой
// что даже элементы индекса меньше
// и нечетные элементы индекса больше
// чем их дальше.

  

function swap(&$a, &$b)

{

    $temp = $a;

    $a = $b;

    $b = $temp;

}

function rearrange(&$arr, $n)

{

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

    {

        if ($i % 2 == 0 && 

            $arr[$i] > $arr[$i + 1])

            swap($arr[$i], $arr[$i + 1]);

  

        if ($i % 2 != 0 && 

            $arr[$i] < $arr[$i + 1])

            swap($arr[$i], $arr[$i + 1]);

    }

}

  
/ * Утилита, которая печатает
массив в строке * /

function printArray(&$arr, $size)

{

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

        echo $arr[$i] . " ";

  

    echo "\n";

}

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

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

$n = sizeof($arr);

  

echo "Before rearranging: \n";

printArray($arr, $n);

  

rearrange($arr, $n);

  

echo "After rearranging: \n";

printArray($arr, $n);

  
// Этот код добавлен
// ChitraNayal
?>


Выход:

Before rearranging:
6 4 2 1 8 3
After rearranging:
4 6 1 8 2 3

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

Ссылка :
discuss.codechef.com/questions/43062/anuund-editorial

Эта статья предоставлена Суканта Нанди . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

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

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

Переупорядочить массив так, чтобы четные элементы индекса были меньше, а нечетные элементы индекса больше

0.00 (0%) 0 votes