Рубрики

Перестановка массива в чередующихся положительных и отрицательных элементах с O (1) дополнительным пробелом | Набор 2

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

Примеры:

Input :
arr[] = {-2, 3, 4, -1}
Output :
arr[] = {-2, 3, -1, 4} OR {-1, 3, -2, 4} OR ..

Input :
arr[] = {-2, 3, 1}
Output :
arr[] = {-2, 3, 1} OR {-2, 1, 3} 

Input : 
arr[] = {-5, 3, 4, 5, -6, -2, 8, 9, -1, -4}
Output :
arr[] = {-5, 3, -2, 5, -6, 4, -4, 9, -1, 8} 
        OR ..

Мы настоятельно рекомендуем вам свернуть браузер и попробовать это в первую очередь.

Мы уже обсуждали решение O (n 2 ), которое поддерживает порядок появления в массиве здесь . Если нам разрешат изменить порядок появления, мы можем решить эту проблему в O (n) времени и O (1) пространстве.

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

Ниже приводится реализация вышеуказанной идеи.

C ++

// C ++ программа для перестановки массива поочередно
// положительные и отрицательные элементы с O (1) дополнительным пробелом
#include <bits/stdc++.h>

using namespace std;

  
// Функция перестановки положительного и отрицательного
// целые числа по-другому. Нижеприведенное
// решение не поддерживает первоначальный порядок
// элементы

void rearrange(int arr[], int n)

{

    int i = -1, j = n;

  

    // сдвигаем все отрицательные значения до конца

    while (i < j)

    {

        while (arr[++i] > 0);

        while (arr[--j] < 0);

        if (i < j)

            swap(arr[i], arr[j]);

    }

  

    // у меня есть индекс самого левого отрицательного элемента

    if (i == 0 || i == n)

        return;

  

    // начинаем с первого положительного элемента с индексом 0

  

    // Переставляем массив в чередующемся положительном &

    // отрицательные элементы

    int k = 0;

    while (k < n && i < n)

    {

        // меняем следующий положительный элемент на четную позицию

        // из следующего отрицательного элемента.

        swap(arr[k], arr[i]);

        i = i + 1;

        k = k + 2;

    }

}

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

void printArray(int arr[], int n)

{

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

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

    cout << endl;

}

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

int main()

{

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

  

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

  

    cout << "Given array is \n";

    printArray(arr, n);

  

    rearrange(arr, n);

  

    cout << "Rearranged array is \n";

    printArray(arr, n);

  

    return 0;

}

Джава

// Java программа для перестановки массива поочередно
// положительные и отрицательные элементы с O (1) дополнительным пробелом

class GFG {

  

  
// Функция перестановки положительного и отрицательного
// целые числа по-другому. Нижеприведенное
// решение не поддерживает первоначальный порядок
// элементы

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

    int i = -1, j = n; 

  

    // сдвигаем все отрицательные значения до конца

    while (i < j) 

    

        while (arr[++i] > 0); 

        while (arr[--j] < 0); 

        if (i < j) 

            swap(arr, i,j); 

    

  

    // у меня есть индекс самого левого отрицательного элемента

    if (i == 0 || i == n) 

        return

  

    // начинаем с первого положительного элемента с индексом 0

  

    // Переставляем массив в чередующемся положительном &

    // отрицательные элементы

    int k = 0

    while (k < n && i < n) 

    

        // меняем следующий положительный элемент на четную позицию

        // из следующего отрицательного элемента.

        swap(arr,k,i); 

        i = i + 1

        k = k + 2

    

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

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

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

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

       System.out.println("");

  

  

static void swap(int arr[], int index1, int index2){

    int c = arr[index1];

    arr[index1]=arr[index2];

    arr[index2]=c;

  

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

    public static void main(String[] args) {

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

  

    int n = arr.length; 

  

    System.out.println("Given array is "); 

    printArray(arr, n); 

  

    rearrange(arr, n); 

  

    System.out.println("Rearranged array is "); 

    printArray(arr, n); 

    }

  

  
// Этот код предоставлен 29AjayKumar

python3

# Python3 программа для перестановки массива
# в чередующемся положительном и отрицательном
# элементов с O (1) дополнительным пробелом

  
# Функция перестановки положительного и
# отрицательные целые числа по-другому.
# Приведенное ниже решение не поддерживает
# оригинальный порядок элементов

def rearrange(arr, n): 

    i = 0

    j = n - 1

  

    # сдвинуть все отрицательные значения

    # к концу

    while (i < j): 

        while (arr[i] > 0):

            i += 1

        while (arr[j] < 0):

            j -= 1

        if (i < j): 

            temp = arr[i] 

            arr[i] = arr[j] 

            arr[j] = temp 

              

    # у меня есть индекс левого

    # отрицательный элемент

    if (i == 0 or i == n): 

        return 0

  

    # начать с первого положительного элемента

    # по индексу 0

  

    # Переставить массив в переменный

    # положительные и отрицательные позиции

    k = 0

    while (k < n and i < n): 

          

        # поменять местами следующий положительный элемент

        # позиция от следующего отрицательного элемента.

        temp = arr[k] 

        arr[k] = arr[i] 

        arr[i] = temp 

        i = i + 1

        k = k + 2

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

def printArray(arr, n): 

    for i in range(n): 

        print(arr[i], end = " "

    print("\n"

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

arr = [2, 3, -4, -1, 6, -9

  

n = len(arr) 

  

print( "Given array is"

printArray(arr, n) 

  
rearrange(arr, n) 

  

print( "Rearranged array is"

printArray(arr, n) 

  
# Этот код добавлен
# Принчи Сингх

C #

// C # программа для перестановки массива
// в чередующемся положительном и отрицательном
// элементы с O (1) дополнительным пробелом

using System;

  

class GFG

{

  
// Функция перестановки положительного и
// отрицательные целые числа по-другому.
// Приведенное ниже решение не поддерживает
// оригинальный порядок элементов

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

    int i = -1, j = n; 

  

    // сдвигаем все отрицательные значения

    // к концу

    while (i < j) 

    

        while (arr[++i] > 0); 

        while (arr[--j] < 0); 

        if (i < j) 

            swap(arr, i,j); 

    

  

    // у меня индекс слева

    // отрицательный элемент

    if (i == 0 || i == n) 

        return

  

    // начинаем с первого положительного

    // элемент с индексом 0

  

    // Переставляем массив поочередно

    // положительные и отрицательные позиции

    int k = 0; 

    while (k < n && i < n) 

    

        // меняем следующий положительный элемент

        // в четной позиции от следующего

        // отрицательный элемент.

        swap(arr, k, i); 

        i = i + 1; 

        k = k + 2; 

    

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

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

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

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

    Console.WriteLine(""); 

  

static void swap(int []arr, int index1,

                            int index2)

    int c = arr[index1]; 

    arr[index1] = arr[index2]; 

    arr[index2] = c; 

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

public static void Main() 

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

  

    int n = arr.Length; 

      

    Console.WriteLine("Given array is "); 

    printArray(arr, n); 

      

    rearrange(arr, n); 

      

    Console.WriteLine("Rearranged array is "); 

    printArray(arr, n); 


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

PHP

<?php 
// PHP программа для перестановки массива
// в чередующемся положительном и отрицательном
// элементы с O (1) дополнительным пробелом

  
// Функция перестановки положительного и
// отрицательные целые числа по-другому.
// Приведенное ниже решение не поддерживает
// оригинальный порядок элементов

function rearrange(&$arr, $n)

{

    $i = -1;

    $j = $n;

  

    // сдвигаем все отрицательные значения

    // к концу

    while ($i < $j)

    {

        while ($arr[++$i] > 0);

        while ($arr[--$j] < 0);

        if ($i < $j)

        {

            $temp = $arr[$i];

            $arr[$i] = $arr[$j];

            $arr[$j] = $temp;

        }         

    }

  

    // у меня индекс слева

    // отрицательный элемент

    if ($i == 0 || $i == $n)

        return;

  

    // начинаем с первого положительного элемента

    // по индексу 0

  

    // Переставляем массив поочередно

    // положительные и отрицательные позиции

    $k = 0;

    while ($k < $n && $i < $n)

    {

        // поменять местами следующий положительный элемент

        // позиция от следующего отрицательного элемента.

        $temp = $arr[$k];

        $arr[$k] = $arr[$i];

        $arr[$i] = $temp;

        $i = $i + 1;

        $k = $k + 2;

    }

}

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

function printArray(&$arr, $n)

{

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

    echo $arr[$i] . " ";

    echo "\n";

}

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

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

  

$n = sizeof($arr);

  

echo "Given array is \n";

printArray($arr, $n);

  

rearrange($arr, $n);

  

echo "Rearranged array is \n";

printArray($arr, $n);

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


Выход:

Given array is 
2 3 -4 -1 6 -9 
Rearranged array is 
-1 3 -4 2 -9 6 

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

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

Перестановка массива в чередующихся положительных и отрицательных элементах с O (1) дополнительным пробелом | Набор 2

0.00 (0%) 0 votes