0-ից և 1-ից առանձնացրեք զանգվածում


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են Ակոլիտ Amazon Ֆաբ MakeMyTrip- ը PayPal Paytm Zoho
Դասավորություն

Խնդիրի հայտարարություն

Ենթադրենք, որ դուք ունեք ամբողջ թիվ զանգված «Rayանգվածում առանձնացնել 0-ը և 1-ը» խնդիրը պահանջում է զանգվածը բաժանել երկու մասի ՝ 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-երը զանգվածում: Arանգվածը վերադասավորեք այնպես, որ բոլոր զրոները տեղափոխվեն զանգվածի ձախ կողմում, և զանգվածի բոլոր 1 տարրերը կտեղափոխվեն զանգվածի աջ կողմ: Դրա համար մենք պատրաստվում ենք հաշվարկել բոլոր զրոները: Այդ զրոյական միավորները կօգնեն մեզ նշելու զանգվածի ձախ մասում զրոները:

Կոդում առաջին անգամ անցեք զանգվածը ՝ զանգվածի բոլոր զրոների հաշվարկը ստանալու համար, այս հաշվարկը կօգնի մեզ նշելու զանգվածի ձախ կողմի բոլոր տեղերի քանակը: Այսպիսով, դրա համար մենք կկողմնորոշենք զանգվածը և ստուգենք arr- ի յուրաքանչյուր i արժեքը, արդյո՞ք այն հավասար է 0-ի, եթե պարզվում է, որ հավասար է 0-ի, ապա հաշվարկի արժեքը կավելացնենք 1-ով: Մենք պետք է հայտարարեինք և նախքան օղակը մտնելը հաշվարկի արժեքը նախանշեց 0-ի: Տարածելուց հետո մենք ստացանք հաշվարկը:

Մենք շրջանցելու ենք օղակների քանակը ոչ մի անգամ և նշելու է arr [i] - ի յուրաքանչյուր արժեք 0-իցth ինդեքսը հաշվարկի -1 տեղերի քանակին: Այժմ զանգվածի ձախ մասում ունենք զրոներ: Այժմ մենք պետք է զանգվածը անցնենք հաշվարկից դեպի n, որտեղ n զանգվածի երկարությունն է: Այսպիսով, սկսած i = հաշվելուց, որն էլ լինի հաշվարկի արժեքը, շարունակեք բոլոր արժեքները թարմացնել 1-ով: Բոլոր գործողություններից հետո մենք ունենք ցանկալի զանգված `զանգվածի ձախ կողմում 0s և զանգվածի աջ կողմում 1s: ,

0-ից և 1-ից առանձնացրեք զանգվածում

Իրականացման

C ++ ծրագիր Array- ի առանձնացնել 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 ծրագիր Array- ի առանձնացնել 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-ների համար

Timeամանակի բարդություն

O (n) որտեղ «Ն» զանգվածում տարրերի քանակն է:

Տիեզերական բարդություն

O (n) որտեղ «Ն» զանգվածում տարրերի քանակն է:

Մանրամասն