Рубрики

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

Массивы

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

Примеры :

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

Input:  arr[] = {-5, -2, 5, 2, 4, 7, 1, 8, 0, -8}
output: arr[] = {-5, 5, -2, 2, -8, 4, 7, 1, 8, 0}

Этот вопрос задавался во многих местах (см. Это и это )

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

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

C ++

/ * C ++ программа для перестановки положительных и отрицательных целых чисел в альтернативных

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

#include <iostream>
#include <assert.h>

using namespace std;

  
// Утилита для правого поворота всех элементов между [outofplace, cur]

void rightrotate(int arr[], int n, int outofplace, int cur)

{

    char tmp = arr[cur];

    for (int i = cur; i > outofplace; i--)

        arr[i] = arr[i-1];

    arr[outofplace] = tmp;

}

  

void rearrange(int arr[], int n)

{

    int outofplace = -1;

  

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

    {

        if (outofplace >= 0)

        {

            // найти предмет, который нужно переместить в неуместное место

            // запись, если запись вне места является положительной и текущей

            // запись отрицательная ИЛИ, если запись вне места отрицательна

            // и текущая запись отрицательна, затем повернуть вправо

            //

            // [...- 3, -4, -5, 6 ...] -> [... 6, -3, -4, -5 ...]

            // ^ ^

            // | |

            // вне места -> вне места

            //

            if (((arr[index] >= 0) && (arr[outofplace] < 0))

                || ((arr[index] < 0) && (arr[outofplace] >= 0)))

            {

                rightrotate(arr, n, outofplace, index);

  

                // новая запись не на своем месте теперь на 2 шага впереди

                if (index - outofplace >= 2)

                    outofplace = outofplace + 2;

                else

                    outofplace = -1;

            }

        }

  

  

        // если ни одна запись не была помечена как неуместная

        if (outofplace == -1)

        {

            // проверка неуместна ли текущая запись

            if (((arr[index] >= 0) && (!(index & 0x01)))

                || ((arr[index] < 0) && (index & 0x01)))

            {

                outofplace = index;

            }

        }

    }

}

  
// Вспомогательная функция для печати массива 'arr []' размера 'n'

void printArray(int arr[], int n)

{

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

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

    cout << endl;

}

  
// Драйверная программа для тестирования функции abive

int main()

{

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

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

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

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

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

    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;

}

Джава

class RearrangeArray 

{

    // Утилита для правого поворота всех элементов

    // между [вне места, cur]

    void rightrotate(int arr[], int n, int outofplace, int cur) 

    {

        int tmp = arr[cur];

        for (int i = cur; i > outofplace; i--)

            arr[i] = arr[i - 1];

        arr[outofplace] = tmp;

    }

  

    void rearrange(int arr[], int n) 

    {

        int outofplace = -1;

  

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

        {

            if (outofplace >= 0) 

            {

                // найти предмет, который нужно переместить в неуместное место

                // запись, если запись вне места является положительной и текущей

                // запись отрицательная ИЛИ, если запись вне места отрицательна

                // и текущая запись отрицательна, затем повернуть вправо

                //

                // [...- 3, -4, -5, 6 ...] -> [... 6, -3, -4, -5 ...]

                // ^ ^

                // | |

                // вне места -> вне места

                //

                if (((arr[index] >= 0) && (arr[outofplace] < 0))

                        || ((arr[index] < 0) && (arr[outofplace] >= 0))) 

                {

                    rightrotate(arr, n, outofplace, index);

  

                    // новая запись не на своем месте теперь на 2 шага впереди

                    if (index - outofplace > 2) 

                        outofplace = outofplace + 2;

                    else

                        outofplace = -1;

                }

            }

  

            // если ни одна запись не была помечена как неуместная

            if (outofplace == -1) 

            {

                // проверка неуместна ли текущая запись

                if (((arr[index] >= 0) && ((index & 0x01)==0))

                        || ((arr[index] < 0) && (index & 0x01)==1))

                    outofplace = index;

            }

        }

    }

   

    // Вспомогательная функция для печати массива 'arr []' размера 'n'

    void printArray(int arr[], int n) 

    {

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

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

        System.out.println("");

    }

  

    public static void main(String[] args) 

    {

        RearrangeArray rearrange = new RearrangeArray();

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

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

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

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

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

        int n = arr.length;

  

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

        rearrange.printArray(arr, n);

  

        rearrange.rearrange(arr, n);

  

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

        rearrange.printArray(arr, n);

    }

}

  
// Этот код предоставлен Mayank Jaiswal

python3

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

  
# поворачивает массив вправо один раз
# из индекса 'outOfPlace to cur'

def rightRotate(arr, n, outOfPlace, cur):

    temp = arr[cur]

    for i in range(cur, outOfPlace, -1):

        arr[i] = arr[i - 1]

    arr[outOfPlace] = temp

    return arr

  

def rearrange(arr, n):

    outOfPlace = -1

    for index in range(n):

        if(outOfPlace >= 0):

  

            # если элемент в outOfPlace поместить в

            # отрицательный и если элемент в индексе

            # положительно, мы можем повернуть

            # массив справа или если элемент

            # на месте outOfPlace в положительном и

            # если элемент в индексе отрицателен, мы

            # можно повернуть массив вправо

            if((arr[index] >= 0 and arr[outOfPlace] < 0) or 

               (arr[index] < 0 and arr[outOfPlace] >= 0)):

                arr = rightRotate(arr, n, outOfPlace, index)

                if(index-outOfPlace > 2):

                    outOfPlace += 2

                else:

                    outOfPlace =- 1

                      

        if(outOfPlace == -1):

              

            # условия для A [index] для

            # быть не на своем месте

            if((arr[index] >= 0 and index % 2 == 0) or 

               (arr[index] < 0 and index % 2 == 1)):

                outOfPlace = index

    return arr

  
Код водителя

arr = [-5, -2, 5, 2, 4, 

        7, 1, 8, 0, -8]

  

print("Given Array is:")

print(arr)

  

print("\nRearranged array is:")

print(rearrange(arr, len(arr)))

  
# Этот код добавлен
# Чаран Сай

C #

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

using System;

  

class GFG

{

    // Сервисная функция для вращения вправо

    // все элементы между [outofplace, cur]

    static void rightrotate(int []arr, int n,

                            int outofplace, int cur) 

    {

        int tmp = arr[cur];

        for (int i = cur; i > outofplace; i--)

            arr[i] = arr[i - 1];

        arr[outofplace] = tmp;

    }

  

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

    {

        int outofplace = -1;

  

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

        {

            if (outofplace >= 0) 

            {

                // найти элемент, который необходимо переместить

                // в неуместную запись, если вне

                // место записи положительное и текущее

                // запись отрицательная ИЛИ если неуместна

                // запись отрицательная и текущая запись

                // отрицательно, затем повернуть вправо

                // [...- 3, -4, -5, 6 ...] -> [... 6, -3, -4, -5 ...]

                // ^ ^

                // | |

                // вне места -> вне места

                //

                if (((arr[index] >= 0) &&

                     (arr[outofplace] < 0)) ||

                     ((arr[index] < 0) &&

                     (arr[outofplace] >= 0))) 

                {

                    rightrotate(arr, n, outofplace, index);

  

                    // новая неуместная запись

                    // сейчас на 2 шага впереди

                    if (index - outofplace > 2) 

                        outofplace = outofplace + 2;

                    else

                        outofplace = -1;

                }

            }

  

            // если ни одна запись не была помечена как неуместная

            if (outofplace == -1) 

            {

                // проверка неуместна ли текущая запись

                if (((arr[index] >= 0) &&

                    ((index & 0x01)==0)) || 

                    ((arr[index] < 0) &&

                    (index & 0x01)==1))

                    outofplace = index;

            }

        }

    }

  

    // Утилита для печати

    // массив 'arr []' размера 'n'

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

    {

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

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

        Console.WriteLine("");

    }

  

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

    public static void Main() 

    {

        int []arr = {-5, -2, 5, 2, 4,

                      7, 1, 8, 0, -8};

        int n = arr.Length;

  

        Console.WriteLine("Given array is ");

        printArray(arr, n);

  

        rearrange(arr, n);

  

        Console.WriteLine("RearrangeD array is ");

        printArray(arr, n);

    }

}

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

PHP

<?php 
// PHP программа для перестановки позитива и
// отрицательные целые числа по-другому
// сохраняя порядок положительного
// и отрицательные числа.

  
// Сервисная функция, чтобы повернуть все вправо
// элементы между [outofplace, cur]

function rightrotate(&$arr, $n, 

                      $outofplace, $cur)

{

    $tmp = $arr[$cur];

    for ($i = $cur; $i > $outofplace; $i--)

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

    $arr[$outofplace] = $tmp;

}

  

function rearrange(&$arr, $n)

{

    $outofplace = -1;

  

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

    {

        if ($outofplace >= 0)

        {

            // найти элемент, который необходимо переместить

            // в неуместную запись, если

            // неуместный вход положительный и

            // текущая запись отрицательна ИЛИ если

            // неуместная запись отрицательна

            // и текущая запись отрицательна

            // правый поворот

            // [...- 3, -4, -5, 6 ...] -> [... 6, -3, -4, -5 ...]

            // ^ ^

            // | |

            // вне места -> вне места

            //

            if ((($arr[$index] >= 0) && ($arr[$outofplace] < 0)) || 

                (($arr[$index] < 0) && ($arr[$outofplace] >= 0)))

            {

                rightrotate($arr, $n, $outofplace, $index);

  

                // новая неуместная запись

                // теперь на 2 шага впереди

                if ($index - $outofplace > 2)

                    $outofplace = $outofplace + 2;

                else

                    $outofplace = -1;

            }

        }

  

        // если ни одна запись не была помечена как неуместная

        if ($outofplace == -1)

        {

            // проверка неуместна ли текущая запись

            if ((($arr[$index] >= 0) && (!($index & 0x01)))

                || (($arr[$index] < 0) && ($index & 0x01)))

            {

                $outofplace = $index;

            }

        }

    }

}

  
// Утилита для печати
// массив 'arr []' размера 'n'

function printArray(&$arr, $n)

{

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

    echo $arr[$i]." ";

    echo "\n";

}

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

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

$arr = array(-5, -2, 5, 2, 4, 7, 1, 8, 0, -8);

$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
-5 -2 5 2 4 7 1 8 0 -8
Rearranged array is
-5 5 -2 2 -8 4 7 1 8 0

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

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

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

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

0.00 (0%) 0 votes