Перемістіть усі негативні елементи в кінець по порядку з додатковим місцем


Рівень складності Легко
Часто запитують у Capital One Citrix IBM SAP Labs Таксі4Звичайно Twilio
масив

Постановка проблеми

“Перемістити всі від’ємні елементи до кінця в порядку з додатковим пробілом” говорить, що вам дано масив, що містить і позитивні, і від’ємні числа. Постановка задачі просить перемістити всі негативні елементи в останню частину масиву.

Приклад

arr[] = { 1,2,-3,-5,2,7,-9,-11 }
1, 2, 2, 7, -3, -5, -9, -11
Пояснення: Усі від’ємні значення були зміщені в останню частину масиву. І вони також у початковому порядку.

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

1. Declare an array same as the size of the original array.
2. Traverse the array and check if any number is greater than or equal to 0,
    1. If true then copy that number from the 0th position of the array we created.
3. Now traverse the array and check if any of the numbers is less than 0.
    1. If true, then copy that value to the array we created from the next position where the positive number ends.
4. Now copy that temporary array we created into the original array and print that array.

Пояснення

Нам дають ціле масив, що містить як негативні, так і додатні числа. Ми попросили переставити масив таким чином, щоб нам довелося перенести всі негативні елементи в останній / кінець масиву. Тоді ми будемо обводити масив для позитивних та негативних елементів окремо. По-перше, ми маємо виконувати операції над позитивними елементами, де ми повинні відтягувати їх ліворуч. А потім змістіть усі негативні елементи вправо.

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

Під час обходу ми перевіримо, чи є елементи масиву більшими або дорівнюють 0, а потім скопіюємо цей елемент лише у тимчасовий масив із початкової позиції тимчасового масиву. Крім того, ми одночасно збільшуємо значення індексу, тому, оскільки ми востаннє копіюємо позитивний елемент, ми маємо індекс значення як наступний елемент, де він повинен зберігатися, за допомогою цього ми будемо виштовхувати всі негативні елементи в останню чергу.

Тепер ми перейдемо до обходу масиву ще раз і перевіримо, чи кожен з елементів менше 0, якщо він дорівнює нулю, тоді почнемо виштовхувати це значення у тимчасовий масив із значення індексу, де ми зупинилися. Нарешті, скопіюйте цей масив до вихідного масиву, потім роздрукуйте його або просто роздрукуйте тимчасовий масив, обидва - це однакові речі. І ми отримуємо необхідний результат.

Перемістіть усі негативні елементи в кінець по порядку з додатковим місцем

код

Код С ++ для переміщення всіх від’ємних елементів у кінець у порядку з додатковим місцем

#include<bits/stdc++.h>
using namespace std;

void segregateElements(int arr[], int n)
{
    int temp[n];

    int j = 0;

    for (int i = 0; i < n ; i++)
        if (arr[i] >= 0 )
            temp[j++] = arr[i];

    if (j == n || j == 0)
        return;

    for (int i = 0 ; i < n ; i++)
        if (arr[i] < 0)
            temp[j++] = arr[i];

    memcpy(arr, temp, sizeof(temp));
}

void printArray(int arr[], int n)
{
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
}

int main()
{
    int arr[] = { 1,2,-3,-5,2,7,-9,-11 };
    int n = sizeof(arr)/sizeof(arr[0]);

    segregateElements(arr, n);
    printArray(arr,n);

    return 0;
}
1 2 2 7 -3 -5 -9 -11

Код Java для переміщення всіх негативних елементів у кінець у порядку з додатковим місцем

import java.util.Arrays;

class moveNegativeElement
{
    public static void segregateElements(int arr[], int n)
    {
        int temp[] = new int[n];

        int j = 0;

        for (int i = 0; i < n; i++)
            if (arr[i] >= 0)
                temp[j++] = arr[i];

        if (j == n || j == 0)
            return;

        for (int i = 0; i < n; i++)
            if (arr[i] < 0)
                temp[j++] = arr[i];

        for (int i = 0; i < n; i++)
            arr[i] = temp[i];
    }
    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 arg[])
    {
        int arr[] = { 1,2,-3,-5,2,7,-9,-11 };
        int n = arr.length;

        segregateElements(arr, n);
        printArray(arr,n);

    }
}
1 2 2 7 -3 -5 -9 -11

Аналіз складності

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

O (N) де "N" є елементами масиву. Ми просто перейшли масив, завдяки якому досягли лінійної складності в часі.

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

O (N) де "N" є елементами масиву. Ми створили додатковий масив для тимчасового використання, де ми зберегли елементи потрібним чином.