将数组中的0和1分开  


难度级别 易得奖学金
经常问 ol石 亚马逊 晶圆厂 MakeMyTrip 贝宝 Paytm 百会
排列

问题陈述  

假设您有一个 整数 大批。 问题“将数组中的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存储在数组中。 重新排列数组,以使所有零都移到数组的左侧,并且数组的所有1s元素都将移到数组的右侧。 为此,我们将对所有零进行计数。 零计数将帮助我们在数组的左侧标记零。

参见
下一个更大的元素

第一次在代码中遍历数组以获取数组中所有零的计数,此计数将帮助我们从数组左侧标记所有计数的位数。 因此,我们将遍历数组并检查arr [i]的每个值是否等于0,如果发现等于0,则将count的值增加1。我们应该声明并在进入循环之前将count的值初始化为0。 遍历后,我们得到了计数。

我们将不遍历循环计数,并从0标记arr [i]的每个值th 索引到count-1个位置。 现在,我们在数组的左侧有零。 现在我们必须遍历数组,从计数到n,其中n是数组的长度。 因此,从i = count开始,无论count的值是多少,都将所有值更新为1。完成所有操作后,我们得到了所需的数组,在数组的左侧为0,在数组的右侧为1。 。

将数组中的0和1分开Pin

实施   

用于将数组中的0和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

用于将数组中的0和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

数组中分离0和1的复杂度分析  

时间复杂度

O(N) 哪里 “ n” 是数组中元素的数量。

参见
构造矩形Leetcode解决方案

空间复杂度

O(N) 哪里 “ n” 是数组中元素的数量。

参考