Разделение нулей и единиц в массиве


Сложный уровень Легко
Часто спрашивают в Акколит Амазонка Потрясающий MakeMyTrip PayPal Paytm Zoho
массив

Постановка задачи

Предположим, у вас есть целое множество. Задача «Разделить нули и единицы в массиве» требует разделить массив на две части: нули и единицы. 0 должны находиться в левой части массива, а 1 - в правой части массива.

Пример

arr[]={1,0,1,1,0,1,1,0}
0 0 0 1 1 1 1 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.

Объяснение разделения нулей и единиц в массиве

Учитывая массив целых чисел в целых числах, в массиве будут храниться только нули и единицы. Переставьте массив таким образом, чтобы все нули были смещены в левую часть массива, а все элементы массива с единицей были смещены в правую сторону массива. Для этого мы собираемся подсчитать все нули. Эти нулевые значения помогут нам пометить нули в левой части массива.

Пройдите по массиву в первый раз в коде, чтобы получить счетчик всех нулей в массиве, этот счет поможет нам отметить все счетное количество мест с левой стороны массива. Для этого мы пройдемся по массиву и проверим для каждого значения arr [i], равно ли оно 0, если окажется, что оно равно 0, то увеличим значение count на 1. Мы должны были объявить и инициализирует значение count равным 0 перед входом в цикл. После перехода мы получили счет.

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

Разделение нулей и единиц в массиве

Реализация

Программа C ++ для разделения нулей и единиц в массиве

#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 для разделения нулей и единиц в массиве

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

Анализ сложности для разделения нулей и единиц в массиве

Сложность времени

О (п) в котором «Н» это количество элементов в массиве.

Космическая сложность

О (п) в котором «Н» это количество элементов в массиве.

Справка