Перемістіть усі від’ємні числа на Початок і Позитив на Кінець постійним додатковим пробілом


Рівень складності Легко
Часто запитують у Capgemini Похід MAQ o9 розчини TCS
масив Сортування

Припустимо, у вас є масив цілих чисел. Він складається як з негативних, так і з позитивних чисел, і постановка задачі просить зрушити / перемістити всі негативні та позитивні елементи вліво від масиву та вправо від масиву, не використовуючи зайвого простору. Це буде рішенням для переміщення всіх від’ємних чисел до початку і від позитивного до кінця з постійним додатковим пробілом.

Приклад

 Вхідний сигнал:

arr[]={2,4,-10,13,-7,-60,52,8,-19 }

вихід:

-10-7 -60 -19 4 2 52 8 13

Пояснення: Оскільки всі числа зміщені вліво, а всі позитивні числа - вправо.

Перемістіть усі від’ємні числа на Початок і Позитив на Кінець постійним додатковим пробілом

Алгоритм

  1. Встановіть j на 0.
  2. Перехід масиву від 0 до n (виключно, де n - довжина масиву).
    1. Перевірте, чи будь-який елемент масиву менше 0,
      1. Перевірте, чи не повинен я дорівнювати j,
        1. Поміняйте місцями значення індексів arr [i] та arr [j] і збільште значення j.
  3. Друк масиву.

Пояснення щодо Переміщення всіх від’ємних чисел до початку та позитивного до кінця

Нам дається масив цілих чисел, і масив містить позитивні та негативні елементи. Ми попросили зрушити всі негативні елементи вліво, а додатні числа вправо. Для цього ми збираємось обмін всі числа, які є позитивними та негативними елементами. Спочатку оберніть масив, а потім перевірте наявність від’ємних чисел, якщо число від’ємне, тоді лише ми підемо на обмін значеннями.

Встановіть для значення j значення 0, воно буде використано для альтернативного значення, яке потрібно поміняти місцями. Ми почнемо обводити масив і перевірятимемо кожне число, оскільки arr [i] менше 0, якщо менше 0, це означає, що ми знайшли від’ємне число, і тому ми перевіримо, чи обидва індекси не однакові, якщо всі вищезазначені умови є істинними, тоді ми поміняємо місцями цифри, оскільки arr [i] та arr [j] поміняємо місцями, і збільшимо значення j. ми будемо продовжувати обхід, поки всі можливі значення не будуть пройдені, замінені та переставлені відповідно до заданої умови.

Ми перевірили, що умова arr [i] менше 0, оскільки ми просто розміщуємо від'ємні числа, всі від'ємні числа після обміну будуть розташовані ліворуч від масиву, а всі інші додатні числа будуть розташовані автоматично праворуч масиву. Після всього обміну, який ми зробили, нам просто потрібно надрукувати масив, в якому виконувались операції підкачки.

Реалізація

Програма C ++ для переміщення всіх від’ємних чисел на початок та позитивних на кінець

#include<iostream>

using namespace std;

void shiftIntegers(int arr[], int n)
{
    int j = 0;
    for (int i = 0; i < n; i++)
    {
        if (arr[i] < 0)
        {
            if (i != j)
                swap(arr[i], arr[j]);
            j++;
        }
    }
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
}
int main()
{
    int arr[] = { 2,4,-10,13,-7,-60,52,8,-19 };
    int n = sizeof(arr) / sizeof(arr[0]);
    shiftIntegers(arr, n);

    return 0;
}
-10 -7 -60 -19 4 2 52 8 13

Програма Java для переміщення всіх від’ємних чисел у початкові та позитивні в кінці

class rearrangeNegativePositive
{
    public static void shiftIntegers(int arr[], int n)
    {
        int j = 0, temp;
        for (int i = 0; i < n; i++)
        {
            if (arr[i] < 0)
            {
                if (i != j)
                {
                    temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
                j++;
            }
        }
    }
    public 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[] = { 2,4,-10,13,-7,-60,52,8,-19 };
        int n = arr.length;

        shiftIntegers(arr, n);
        printArray(arr, n);
    }
}
-10 -7 -60 -19 4 2 52 8 13

Аналіз складності для переміщення всіх від’ємних чисел до початку та позитивного до кінця

Складність часу

О (п) де "N" - кількість елементів у масиві.

Складність простору

O (1) оскільки додатковий простір не потрібен.

Висновок

Це програма для переміщення всіх від’ємних чисел на початок та позитивне на кінець з постійним додатковим простором у Java та C ++.

Посилання