Рубрики

Переставьте положительные и отрицательные числа в O (n) время и O (1) дополнительное пространство

Массив содержит как положительные, так и отрицательные числа в случайном порядке. Переставьте элементы массива так, чтобы положительные и отрицательные числа размещались попеременно. Количество положительных и отрицательных чисел не должно быть одинаковым. Если есть больше положительных чисел, они появляются в конце массива. Если есть больше отрицательных чисел, они тоже появляются в конце массива.

Например, если входным массивом является [-1, 2, -3, 4, 5, 6, -7, 8, 9], то выходной сигнал должен быть [9, -7, 8, -3, 5, — 1, 2, 4, 6]

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

Решение состоит в том, чтобы сначала отделить положительные и отрицательные числа, используя процесс разбиения QuickSort. В процессе разбиения рассматривайте 0 как значение элемента pivot, чтобы все отрицательные числа были помещены перед положительными числами. Как только отрицательные и положительные числа разделены, мы начинаем с первого отрицательного числа и первого положительного числа и заменяем каждое альтернативное отрицательное число следующим положительным числом.

C ++

// Программа на C ++ для положительного результата
// числа с четными индексами (0, 2, 4, ..)
// и отрицательные числа в нечетном
// индексы (1, 3, 5, ..)
#include <iostream>

using namespace std;

  

class GFG

{

    public:

    void rearrange(int [],int);

    void swap(int *,int *);

    void printArray(int [],int);

};

  
// Основная функция, которая переставляет
// элементы данного массива. Ставит
// положительные элементы при четных индексах
// (0, 2, ..) и отрицательные числа
// по нечетным индексам (1, 3, ..).

void GFG :: rearrange(int arr[], int n)

{

    // Следующие несколько строк

    // похоже на процесс разбиения

    // быстрой сортировки. Идея состоит в том, чтобы

    // рассматриваем 0 как точку опоры и

    // делим массив вокруг него.

    int i = -1;

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

    {

        if (arr[j] < 0)

        {

            i++;

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

        }

    }

  

    // Теперь все положительные числа в

    // конечные и отрицательные числа в

    // начало массива. Initialize

    // индексы для начальной точки

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

    // чтобы поменяться местами

    int pos = i + 1, neg = 0;

  

    // Увеличиваем отрицательный индекс на

    // 2 и положительный индекс на 1,

    // т.е. меняем каждый альтернативный минус

    // номер со следующим положительным числом

    while (pos < n && neg < pos && 

                     arr[neg] < 0)

    {

        swap(&arr[neg], &arr[pos]);

        pos++;

        neg += 2;

    }

}

  
// функция полезности
// поменять местами два элемента

void GFG :: swap(int *a, int *b)

{

    int temp = *a;

    *a = *b;

    *b = temp;

}

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

void GFG :: printArray(int arr[], int n)

{

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

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

}

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

int main() 

{

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

                  5, 6, -7, 8, 9};

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

    GFG test;

    test.rearrange(arr, n);

    test.printArray(arr, n);

    return 0;

}

  
// Этот код добавлен
// от vt_Yogesh Shukla 1

С

// Программа на C ++ для помещения положительных чисел в четные индексы (0,
// 2, 4, ..) и отрицательные числа при нечетных индексах (1, 3, 5, ..)
#include <stdio.h>

  
// прототип для обмена

void swap(int *a, int *b);

  
// Основная функция, которая переставляет элементы данного массива.
// Он помещает положительные элементы в четные индексы (0, 2, ..) и
// отрицательные числа при нечетных индексах (1, 3, ..).

void rearrange(int arr[], int n)

{

    // Следующие несколько строк похожи на процесс разбиения

    // быстрой сортировки. Идея состоит в том, чтобы рассматривать 0 как опору и

    // делим массив вокруг него.

    int i = -1;

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

    {

        if (arr[j] < 0)

        {

            i++;

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

        }

    }

  

    // Теперь все положительные числа в конце и отрицательные числа

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

    // точка положительных и отрицательных чисел, подлежащих обмену

    int pos = i+1, neg = 0;

  

    // Увеличиваем отрицательный индекс на 2 и положительный индекс на 1,

    // т.е. меняем каждое альтернативное отрицательное число на следующее

    // положительное число

    while (pos < n && neg < pos && arr[neg] < 0)

    {

        swap(&arr[neg], &arr[pos]);

        pos++;

        neg += 2;

    }

}

  
// Утилита для замены двух элементов

void swap(int *a, int *b)

{

    int temp = *a;

    *a = *b;

    *b = temp;

}

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

void printArray(int arr[], int n)

{

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

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

}

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

int main()

{

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

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

    rearrange(arr, n);

    printArray(arr, n);

    return 0;

}

Джава

// JAVA-программа для размещения положительных чисел на четных индексах
// (0, 2, 4, ..) и отрицательные числа при нечетных индексах (1, 3,
// 5, ..)

import java.io.*;

  

class Alternate {

  

    // Основная функция, которая переставляет элементы данного

    // массив. Он помещает положительные элементы в четные индексы (0,

    // 2, ..) и отрицательные числа при нечетных индексах (1, 3, ..).

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

    {

        // Следующие несколько строк похожи на раздел

        // процесс быстрой сортировки. Идея состоит в том, чтобы рассмотреть 0

        // как круг и разделить массив вокруг него.

        int i = -1, temp = 0;

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

        {

            if (arr[j] < 0)

            {

                i++;

                temp = arr[i];

                arr[i] = arr[j];

                arr[j] = temp;

            }

        }

  

        // Теперь все положительные числа в конце и отрицательные числа в

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

        // положительных и отрицательных чисел для обмена

        int pos = i+1, neg = 0;

  

        // Увеличиваем отрицательный индекс на 2 и положительный индекс на 1, т.е.

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

        while (pos < n && neg < pos && arr[neg] < 0)

        {

            temp = arr[neg];

            arr[neg] = arr[pos];

            arr[pos] = temp;

            pos++;

            neg += 2;

        }

    }

  

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

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

    {

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

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

    }

  

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

    public static void main (String[] args)

    {

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

        int n = arr.length;

        rearrange(arr,n);

        System.out.println("Array after rearranging: ");

        printArray(arr,n);

    }

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

питон

# Программа Python для помещения положительных чисел в четные индексы (0, // 2, 4, ..) и
# отрицательные числа при нечетных индексах (1, 3, 5, ..)

  
# Основная функция, которая переставляет элементы данного массива.
# Он помещает положительные элементы в четные индексы (0, 2, ..) и
# отрицательные числа при нечетных индексах (1, 3, ..).

def rearrange(arr, n):

    # Следующие несколько строк похожи на процесс разбиения

    # из быстрой сортировки. Идея состоит в том, чтобы рассматривать 0 как опору и

    # разделить массив вокруг него.

    i = -1

    for j in range(n):

        if (arr[j] < 0):

            i += 1

            # обмен обр

            arr[i], arr[j] = arr[j], arr[i]

   

    # Теперь все положительные числа в конце и отрицательные числа

    # в начале массива. Инициализировать индексы для запуска

    # точка положительных и отрицательных чисел, подлежащих обмену

    pos, neg = i+1, 0

   

    # Увеличить отрицательный индекс на 2 и положительный индекс на 1,

    # т.е. поменяйте местами каждое альтернативное отрицательное число следующим

    # положительное число

    while (pos < n and neg < pos and arr[neg] < 0):

  

        # обмен обр

        arr[neg], arr[pos] = arr[pos], arr[neg]

        pos += 1

        neg += 2

  
# Утилита для печати массива

def printArray(arr, n):

      

    for i in range(n):

        print arr[i],

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

arr = [-1, 2, -3, 4, 5, 6, -7, 8, 9]

n = len(arr)

rearrange(arr, n)
printArray(arr, n)

  
# Предоставлено Afzal

C #

// AC # программа для установки положительных чисел
// на четных индексах (0, 2, 4, ..) и
// отрицательные числа с нечетными индексами (1, 3, 5, ..)

using System;

  

class Alternate {

  

    // Основная функция, которая переставляет элементы

    // данного массива. Это положительные элементы

    // при четных индексах (0, 2, ..) и отрицательных

    // числа с нечетными индексами (1, 3, ..).

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

    {

        // Следующие несколько строк похожи на раздел

        // процесс быстрой сортировки. Идея состоит в том, чтобы рассмотреть 0

        // как круг и разделить массив вокруг него.

        int i = -1, temp = 0;

        for (int j = 0; j < n; j++) {

            if (arr[j] < 0) {

                i++;

                temp = arr[i];

                arr[i] = arr[j];

                arr[j] = temp;

            }

        }

  

        // Теперь все положительные числа в конце

        // и отрицательные числа в начале

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

        // положительных и отрицательных чисел для обмена

        int pos = i + 1, neg = 0;

  

        // Увеличиваем отрицательный индекс на 2 и

        // положительный индекс на 1, т. е. поменять местами каждый

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

        while (pos < n && neg < pos && arr[neg] < 0) {

            temp = arr[neg];

            arr[neg] = arr[pos];

            arr[pos] = temp;

            pos++;

            neg += 2;

        }

    }

  

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

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

    {

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

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

    }

  

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

    public static void Main()

    {

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

        int n = arr.Length;

        rearrange(arr, n);

        printArray(arr, n);

    }

}

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

PHP

<?php
// PHP-программа для положительных чисел
// при четных индексах (0, 2, 4, ..) и отрицательных
// числа с нечетными индексами (1, 3, 5, ..)

  
// Основная функция, которая переставляет элементы
// данного массива. Это положительные элементы
// при четных индексах (0, 2, ..) и отрицательных
// числа с нечетными индексами (1, 3, ..).

function rearrange(&$arr, $n

    // Следующие несколько строк похожи

    // разделить процесс быстрой сортировки.

    // Идея состоит в том, чтобы считать 0 опорным

    // и разделить массив вокруг него.

    $i = -1; 

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

    

        if ($arr[$j] < 0) 

        

            $i++; 

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

        

    

  

    // Теперь все положительные числа в конце и

    // отрицательные числа в начале массива.

    // Инициализируем индексы для начальной точки

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

    $pos = $i + 1;

    $neg = 0; 

  

    // Увеличиваем отрицательный индекс на 2 и

    // положительный индекс на 1, т. е. поменять местами каждый

    // чередуем отрицательное число со следующим

    // положительное число

    while ($pos < $n && $neg < $pos && 

                        $arr[$neg] < 0) 

    

        swap($arr[$neg], $arr[$pos]); 

        $pos++; 

        $neg += 2; 

    

  
// Утилита для замены двух элементов

function swap(&$a, &$b

    $temp = $a

    $a = $b

    $b = $temp

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

function printArray(&$arr, $n

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

        echo " " . $arr[$i] . " "

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

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

$n = count($arr); 

rearrange($arr, $n); 

printArray($arr, $n); 

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


Выход:

    4   -3    5   -1    6   -7    2    8    9

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

Статьи по Теме:
Переставьте положительные и отрицательные числа с постоянным лишним пробелом
Переместите все отрицательные элементы в конец в порядке с дополнительным пробелом

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

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

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

Переставьте положительные и отрицательные числа в O (n) время и O (1) дополнительное пространство

0.00 (0%) 0 votes