Отделете 0 и 1 в масив


Ниво на трудност Лесно
Често задавани в Аколит Амазонка Fab MakeMyTrip PayPal Paytm Zoho
Array

Декларация за проблема

Да предположим, че имате цяло число масив. Проблемът „Разделяне на 0s и 1s в масив” изисква разделянето на масива на две части, на 0s и на 1s. Нулите трябва да са от лявата страна на масива и 0 от дясната страна на масива.

Пример

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 в масив

предвид масив от целите числа, в цели числа, той ще съхранява само 0s и 1s в масива. Пренаредете масива по такъв начин, че всички нули да бъдат изместени в лявата страна на масива и всички 1s елементи на масива да бъдат изместени в дясната страна на масива. За това ще направим преброяване на всички нули. Това броене на нули ще ни помогне при маркирането на нулите от лявата страна на масива.

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

Ние няма да обходим броенето на цикъла нито веднъж и ще маркираме всяка стойност на arr [i] от 0th индекс към броя-1 брой места. Сега имаме нулите в лявата страна на масива. Сега трябва да прехвърлим масива от броя до n, където n е дължината на масива. И така, започвайки от i = count, каквато и да е стойността на count, продължете да актуализирате всички стойности до 1. След всички операции имаме желания масив, 0s в лявата страна на масива и 1s в дясната страна на масива .

Отделете 0 и 1 в масив

изпълнение

C ++ програма за разделени 0s и 1s в масив

#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

Анализ на сложността за разделени 0s и 1s в масив

Сложност във времето

О (п) където "н" е броят на елементите в масива.

Сложност на пространството

О (п) където "н" е броят на елементите в масива.

препратка