Розділіть 0 і 1 в масиві


Рівень складності Легко
Часто запитують у Accolite Амазонка Fab MakeMyTrip PayPal Paymt Zoho
масив

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

Припустимо, у вас є ціле масив. Задача “Поділити 0 і 1 в масиві” просить розділити масив на дві частини, через 0 і за 1. Нулі повинні знаходитись з лівої сторони масиву, а одиниці - з правої сторони масиву.

Приклад

arr[]={1,0,1,1,0,1,1,0}
0 0 0 1 1 1 1 1
Пояснення: Всі 0 зміщуються вліво, а 1 - вправо.

Алгоритм

1. Traverse the array and get the count of total zero’s in the array.
2. Push ‘0’ that

підраховувати кількість разів у масиві

.
3. Push ‘1’ (n – count) no of times in the array from the next position of 0 where we left inserting 0.
4. Print the array.

Пояснення для відокремлених 0 і 1 в масиві

З огляду на масив з цілих чисел, у цілих числах, він буде зберігати лише 0 і 1 в масиві. Впорядкуйте масив таким чином, що всі нулі будуть зміщені в ліву сторону масиву, а всі 1s елементи масиву будуть зміщені в праву сторону масиву. Для цього ми підрахуємо всі нулі. Цей підрахунок нулів допоможе нам позначити нулі в лівій частині масиву.

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

Ми не проходимо підрахунок циклу жодного разу і позначимо кожне значення arr [i] від 0th покажчик до кількості місць count-1. Тепер у нас є нулі в лівій частині масиву. Тепер ми маємо перейти масив від підрахунку до n, де n - довжина масиву. Отже, починаючи з i = count, яким би не було значення count, продовжуйте оновлювати всі значення до 1. Після всіх операцій ми маємо бажаний масив, 0s в лівій частині масиву і 1s в правій частині масиву. .

Розділіть 0 і 1 в масиві

Реалізація

Програма C ++ для відокремлених 0 і 1 в масиві

#include<iostream>

using namespace std;

void segregateZeroesOnes(int arr[], int n)
{
    int count = 0;

    for (int i = 0; i < n; i++)
    {
        if (arr[i] == 0)
            count++;
    }
    for (int i = 0; i < count; i++)
        arr[i] = 0;

    for (int i = count; i < n; i++)
        arr[i] = 1;
}

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

int main()
{
    int arr[] = {1,0,1,1,0,1,1,0};
    int n = sizeof(arr) / sizeof(arr[0]);

    segregateZeroesOnes(arr, n);
    printArray(arr, n);

    return 0;
}
0 0 0 1 1 1 1 1

Програма Java для розділених 0 і 1 в масиві

class segregateZeroesOnes
{
    public static void segregateZeroesOnes(int arr[], int n)
    {
        int count = 0;

        for (int i = 0; i < n; i++)
        {
            if (arr[i] == 0)
                count++;
        }
        for (int i = 0; i < count; i++)
            arr[i] = 0;

        for (int i = count; i < n; i++)
            arr[i] = 1;
    }
    
    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[] = new int[] { 1,0,1,1,0,1,1,0 };
        int n = arr.length;

        segregateZeroesOnes(arr, n);
        printArray(arr, n);

    }
}
0 0 0 1 1 1 1 1

Аналіз складності для відокремлених 0 і 1 в масиві

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

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

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

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

Посилання