Διαχωρίστε 0s και 1s σε μια σειρά


Επίπεδο δυσκολίας Εύκολος
Συχνές ερωτήσεις Απολύτως αμαζόνα Fab MakeMyTrip PayPal Paytm Zoho
Παράταξη

Δήλωση προβλήματος

Ας υποθέσουμε ότι έχετε ένα ακέραιος αριθμός πίνακας. Το πρόβλημα "Διαχωρισμός 0s και 1s σε πίνακα" ζητά να διαχωριστεί ο πίνακας σε δύο μέρη, σε 0s και σε 1s. Τα 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.

Επεξήγηση για το Segregate 0s και 1s σε μια σειρά

Δεδομένης της παράταξη των ακέραιων αριθμών, σε ακέραιους αριθμούς, αποθηκεύει μόνο τα 0 και 1s στον πίνακα. Αναδιάταξη του πίνακα με τέτοιο τρόπο ώστε όλα τα μηδενικά να μετατοπιστούν στην αριστερή πλευρά του πίνακα και όλα τα στοιχεία 1s του πίνακα θα μετατοπιστούν στη δεξιά πλευρά του πίνακα. Για αυτό, θα κάνουμε μια μέτρηση όλων των μηδενικών. Αυτό το μηδέν μετράει θα μας βοηθήσει να σημειώσουμε τα μηδενικά στην αριστερή πλευρά του πίνακα.

Διασχίστε τον πίνακα για πρώτη φορά στον κώδικα για να λάβετε τον αριθμό όλων των μηδενικών στον πίνακα, αυτός ο αριθμός θα μας βοηθήσει να επισημάνουμε όλο τον αριθμό των θέσεων από την αριστερή πλευρά του πίνακα. Έτσι για αυτό θα διασχίσουμε τον πίνακα και θα ελέγξουμε για κάθε τιμή του arr [i], είναι ίσο με 0, αν βρεθεί ότι είναι ίσο με 0, τότε αυξάνουμε την τιμή μέτρησης κατά 1. Θα έπρεπε να δηλώσουμε και αρχικοποίησε την τιμή της μέτρησης στο 0 πριν μπείτε στο βρόχο. Αφού περάσαμε, καταλήξαμε.

Θα διασχίζουμε τον αριθμό των βρόχων χωρίς διαστήματα και θα επισημαίνουμε κάθε τιμή του arr [i] από το 0th ευρετήριο για τον αριθμό-αριθμός θέσεων. Τώρα, έχουμε τα μηδενικά στην αριστερή πλευρά του πίνακα. Τώρα πρέπει να διασχίσουμε τον πίνακα από το πλήθος στο n όπου n είναι το μήκος του πίνακα. Ξεκινώντας λοιπόν από το i = count όποια και αν είναι η τιμή του count, συνεχίστε να ενημερώνετε όλες τις τιμές σε 1. Μετά από όλες τις λειτουργίες, έχουμε τον επιθυμητό πίνακα, 1s στην αριστερή πλευρά του πίνακα και 0s στη δεξιά πλευρά του πίνακα .

Διαχωρίστε 0s και 1s σε μια σειρά

Εκτέλεση

Πρόγραμμα C ++ για Segregate 0s και 1s σε Array

#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 για Segregate 0s και 1s σε Array

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

Ανάλυση πολυπλοκότητας για το Segregate 0s και 1s σε ένα Array

Χρόνος πολυπλοκότητας

O (n) όπου «Ν» είναι ο αριθμός των στοιχείων στον πίνακα.

Διαστημική πολυπλοκότητα

O (n) όπου «Ν» είναι ο αριθμός των στοιχείων στον πίνακα.

Αναφορά