Рубрики

Разделите 0 и 1 в массиве

Вам дан массив из 0 и 1 в случайном порядке. Разделите 0 с левой стороны и 1 с правой стороны массива. Траверс массив только один раз.

Input array   =  [0, 1, 0, 1, 0, 0, 1, 1, 1, 0] 
Output array =  [0, 0, 0, 0, 0, 1, 1, 1, 1, 1] 

Метод 1 (считать 0 или 1)
Спасибо Навину за предложение этого метода.
1) Подсчитайте количество 0. Пусть считать будет C.
2) Как только мы посчитаем, мы можем поместить C 0 в начало и 1 в оставшиеся n — C позиции в массиве.

Сложность времени: O (n)

C ++

// C ++ код для разделения 0 и 1 в массиве
#include <bits/stdc++.h>

using namespace std;

  
// Функция для разделения 0 и 1

void segregate0and1(int arr[], int n)

{

    int count = 0; // Подсчитывает количество нулей в обр

  

    for (int i = 0; i < n; i++) {

        if (arr[i] == 0)

            count++;

    }

  

    // Цикл заполняет arr с 0 до отсчета

    for (int i = 0; i < count; i++)

        arr[i] = 0;

  

    // Цикл заполняет оставшееся пространство arr 1

    for (int i = count; i < n; i++)

        arr[i] = 1;

}

  
// Функция для печати сегрегированного массива

void print(int arr[], int n)

{

    cout << "Array after segregation is ";

  

    for (int i = 0; i < n; i++)

        cout << arr[i] << " ";

}

  
// Функция драйвера

int main()

{

    int arr[] = { 0, 1, 0, 1, 1, 1 };

    int n = sizeof(arr) / sizeof(arr[0]);

      

    segregate0and1(arr, n);

    print(arr, n);

      

    return 0;

}

  
// Этот код предоставлен Sahil_Bansall

Джава

// Java-код для разделения 0 и 1 в массиве

class GFG {

      

    // функция для разделения 0 и 1

    static void segregate0and1(int arr[], int n)

    {

        int count = 0; // подсчитывает количество нулей в обр

      

        for (int i = 0; i < n; i++) {

            if (arr[i] == 0)

                count++;

        }

  

        // цикл заполняет arr с 0 до отсчета

        for (int i = 0; i < count; i++)

            arr[i] = 0;

  

        // цикл заполняет оставшееся пространство arr 1

        for (int i = count; i < n; i++)

            arr[i] = 1;

    }

      

    // функция для печати сегрегированного массива

    static void print(int arr[], int n)

    {

        System.out.print("Array after segregation is ");

        for (int i = 0; i < n; i++)

            System.out.print(arr[i] + " ");    

    }

      

    // функция драйвера

    public static void main(String[] args)

    {

        int arr[] = new int[]{ 0, 1, 0, 1, 1, 1 };

        int n = arr.length;

  

        segregate0and1(arr, n);

        print(arr, n);

          

    }

}

  
// Этот код предоставлен Камалем Равалом

python3

# Python 3 код для разделения
# 0 и 1 в массиве

  
# Функция для разделения 0 и 1

def segregate0and1(arr, n) :

      

    # Подсчитывает количество нулей в обр

    count = 0 

  

    for i in range(0, n) :

        if (arr[i] == 0) :

            count = count + 1

  

    # Цикл заполняет arr с 0 до подсчета

    for i in range(0, count) :

        arr[i] = 0

  

    # Цикл заполняет оставшееся пространство arr 1

    for i in range(count, n) :

        arr[i] = 1

          

  
# Функция для печати сегрегированного массива

def print_arr(arr , n) :

    print( "Array after segregation is ",end = "")

  

    for i in range(0, n) :

        print(arr[i] , end = " ")

          

  
# Функция драйвера

arr = [ 0, 1, 0, 1, 1, 1 ]

n = len(arr)

      
segregate0and1(arr, n)
print_arr(arr, n)

  

  

          
# Этот код предоставлен Никитой Тивари.

C #

// C # код для разделения 0 и 1 в массиве

using System;

  

class GFG {

      

    // функция для разделения 0 и 1

    static void segregate0and1(int []arr, int n)

    {   

        // подсчитывает количество нулей в обр

        int count = 0; 

      

        for (int i = 0; i < n; i++) {

            if (arr[i] == 0)

                count++;

        }

  

        // цикл заполняет arr с 0 до отсчета

        for (int i = 0; i < count; i++)

            arr[i] = 0;

  

        // цикл заполняет оставшееся пространство arr 1

        for (int i = count; i < n; i++)

            arr[i] = 1;

    }

      

    // функция для печати сегрегированного массива

    static void print(int []arr, int n)

    {

        Console.WriteLine("Array after segregation is ");

        for (int i = 0; i < n; i++)

            Console.Write(arr[i] + " "); 

    }

      

    // функция драйвера

    public static void Main()

    {

        int []arr = new int[]{ 0, 1, 0, 1, 1, 1 };

        int n = arr.Length;

  

        segregate0and1(arr, n);

        print(arr, n);

          

    }

}

  
// Этот код предоставлен vt_m.

PHP

<?php
// PHP-код для разделения
// 0 и 1 в массиве

  
// Функция для разделения
// 0 и 1

function segregate0and1(&$arr, $n)

{

    $count = 0; // Считает нет

                // из нулей в обр

  

    for ($i = 0; $i < $n; $i++) 

    {

        if ($arr[$i] == 0)

            $count++;

    }

  

    // Цикл заполняет обр

    // с 0 до подсчета

    for ($i = 0; $i < $count; $i++)

        $arr[$i] = 0;

  

    // цикл заполняет оставшиеся

    // пространство с 1

    for ($i = $count; $i < $n; $i++)

        $arr[$i] = 1;

}

  
// Функция для печати
// разделенный массив

function toprint(&$arr , $n)

{

    echo ("Array after segregation is ");

  

    for ($i = 0; $i < $n; $i++)

        echo ( $arr[$i] . " ");

}

  
// Код драйвера

$arr = array(0, 1, 0, 1, 1, 1 );

$n = sizeof($arr);

  

segregate0and1($arr, $n);

toprint($arr, $n);

      
// Этот код добавлен
// от Shivi_Aggarwal
?>


Выход :

Array after segregation is 0 0 1 1 1 1 

Метод 1 пересекает массив два раза. Метод 2 делает то же самое за один проход.

Способ 2 (использовать два индекса для прохождения)
Поддерживать два индекса. Инициализируйте первый индекс слева как 0, а второй индекс справа как n-1.

Следуйте, пока левый < правый
a) Продолжайте увеличивать индекс влево, пока в нем есть нули
б) Продолжайте уменьшать индекс правильно, пока в нем есть 1
c) Если left <right, то меняйте arr [left] и arr [right]

Реализация:

C ++

// C ++ программа для сортировки двоичного массива за один проход
#include <bits/stdc++.h>

using namespace std;

  
/ * Функция для установки всех нулей слева и всех 1 справа * /

void segregate0and1(int arr[], int size) 

    / * Инициализировать левый и правый индексы * /

    int left = 0, right = size-1; 

  

    while (left < right) 

    

        / * Увеличиваем левый индекс, пока мы видим 0 слева * /

        while (arr[left] == 0 && left < right) 

            left++; 

  

        / * Уменьшить правый индекс, пока мы видим 1 справа * /

        while (arr[right] == 1 && left < right) 

            right--; 

  

        / * Если слева меньше, чем справа, то слева 1

        и 0 справа. Обмен arr [влево] и arr [вправо] * /

        if (left < right) 

        

            arr[left] = 0; 

            arr[right] = 1; 

            left++; 

            right--; 

        

    

  
/ * Код водителя * /

int main() 

    int arr[] = {0, 1, 0, 1, 1, 1}; 

    int i, arr_size = sizeof(arr)/sizeof(arr[0]); 

  

    segregate0and1(arr, arr_size); 

  

    cout << "Array after segregation "

    for (i = 0; i < 6; i++) 

        cout << arr[i] << " "

    return 0; 

  
// Это код, предоставленный rathbhupendra

С

// C программа для сортировки двоичного массива за один проход
#include<stdio.h>

  
/ * Функция для установки всех нулей слева и всех 1 справа * /

void segregate0and1(int arr[], int size)

{

    / * Инициализировать левый и правый индексы * /

    int left = 0, right = size-1;

  

    while (left < right)

    {

        / * Увеличиваем левый индекс, пока мы видим 0 слева * /

        while (arr[left] == 0 && left < right)

            left++;

  

        / * Уменьшить правый индекс, пока мы видим 1 справа * /

        while (arr[right] == 1 && left < right)

            right--;

  

        / * Если слева меньше, чем справа, то слева 1

          и 0 справа. Обмен arr [влево] и arr [вправо] * /

        if (left < right)

        {

            arr[left] = 0;

            arr[right] = 1;

            left++;

            right--;

        }

    }

}

  
/ * программа для тестирования драйверов * /

int main()

{

    int arr[] = {0, 1, 0, 1, 1, 1};

    int i, arr_size = sizeof(arr)/sizeof(arr[0]);

  

    segregate0and1(arr, arr_size);

  

    printf("Array after segregation ");

    for (i = 0; i < 6; i++)

        printf("%d ", arr[i]);

  

    getchar();

    return 0;

}

Джава

class Segregate 

{

    / * Функция для установки всех нулей слева и всех 1 справа * /

    void segregate0and1(int arr[], int size) 

    {

        / * Инициализировать левый и правый индексы * /

        int left = 0, right = size - 1;

  

        while (left < right) 

        {

            / * Увеличиваем левый индекс, пока мы видим 0 слева * /

            while (arr[left] == 0 && left < right)

               left++;

  

            / * Уменьшить правый индекс, пока мы видим 1 справа * /

            while (arr[right] == 1 && left < right)

                right--;

  

            / * Если слева меньше, чем справа, то слева 1

               и 0 справа. Обмен arr [влево] и arr [вправо] * /

            if (left < right) 

            {

                arr[left] = 0;

                arr[right] = 1;

                left++;

                right--;

            }

        }

    }

      

    / * Программа драйвера для проверки вышеуказанных функций * /

    public static void main(String[] args) 

    {

        Segregate seg = new Segregate();

        int arr[] = new int[]{0, 1, 0, 1, 1, 1};

        int i, arr_size = arr.length;

  

        seg.segregate0and1(arr, arr_size);

  

        System.out.print("Array after segregation is ");

        for (i = 0; i < 6; i++)

            System.out.print(arr[i] + " ");

    }

}

питон

# Программа Python для сортировки двоичного массива за один проход

  
# Функция для установки всех нулей слева и всех 1 справа

def segregate0and1(arr, size):

    # Инициализировать левый и правый индексы

    left, right = 0, size-1

      

    while left < right:

        # Увеличиваем левый индекс, пока мы видим 0 слева

        while arr[left] == 0 and left < right:

            left += 1

  

        # Уменьшить индекс справа, пока мы видим 1 справа

        while arr[right] == 1 and left < right:

            right -= 1

  

        # Если слева меньше, чем справа, то слева 1

        # и 0 справа. Обмен arr [слева] и arr [справа]

        if left < right:

            arr[left] = 0

            arr[right] = 1

            left += 1

            right -= 1

  

    return arr

  
# программа для тестирования драйвера

arr = [0, 1, 0, 1, 1, 1]

arr_size = len(arr)

print("Array after segregation")

print(segregate0and1(arr, arr_size))

  
# Этот код предоставлен Pratik Chhajer

C #

// C # программа для сортировки двоичного массива за один проход

using System;

  

class Segregate 

{

    / * Функция для установки всех 0

      слева и все 1 с справа * /

    void segregate0and1(int []arr, int size) 

    {

        / * Инициализировать левый и правый индексы * /

        int left = 0, right = size - 1;

  

        while (left < right) 

        {

            / * Увеличивать левый индекс, пока

               мы видим 0 слева * /

            while (arr[left] == 0 && left < right)

            left++;

  

            / * Уменьшить правый индекс при

               мы видим 1 справа * /

            while (arr[right] == 1 && left < right)

                right--;

  

            / * Если слева меньше, чем справа, то

               1 слева и 0 справа.

               Обмен arr [влево] и arr [вправо] * /

            if (left < right) 

            {

                arr[left] = 0;

                arr[right] = 1;

                left++;

                right--;

            }

        }

    }

      

    / * Программа драйвера для проверки вышеуказанных функций * /

    public static void Main() 

    {

        Segregate seg = new Segregate();

        int []arr = new int[]{0, 1, 0, 1, 1, 1};

        int i, arr_size = arr.Length;

  

        seg.segregate0and1(arr, arr_size);

  

        Console.WriteLine("Array after segregation is ");

        for (i = 0; i < 6; i++)

            Console.Write(arr[i] + " ");

    }

}

  
// Этот код предоставлен vt_m.

PHP

<?php
// PHP программа для сортировки
// двоичный массив за один проход

  
// Функция для установки всех 0
// слева и все 1 с справа

function segregate0and1(&$arr, $size)

{

    // Инициализируем влево и

    // правильные индексы

    $left = 0;

    $right = $size - 1;

  

    while ($left < $right)

    {

        // Увеличиваем левый индекс

        // пока мы видим 0 слева

        while ($arr[$left] == 0 && 

               $left < $right)

            $left++;

  

        // Уменьшаем правый индекс

        // пока мы видим 1 справа

        while ($arr[$right] == 1 && 

               $left < $right)

            $right--;

  

        // Если слева меньше, чем справа

        // тогда слева 1

        // и 0 справа. обмен

        // arr [left] и arr [right]

        if ($left < $right)

        {

            $arr[$left] = 0;

            $arr[$right] = 1;

            $left++;

            $right--;

        }

    }

}

  
// Код драйвера

$arr = array(0, 1, 0, 1, 1, 1);

$arr_size = sizeof($arr);

  

segregate0and1($arr, $arr_size);

  

printf("Array after segregation is ");

for ($i = 0; $i < 6; $i++)

    echo ($arr[$i]. " ");

  
// Этот код добавлен
// от Shivi_Aggarwal
?>


Выход:

Array after segregation is 0 0 1 1 1 1 

Сложность времени: O (n)

Другой подход:
1. Возьмите два указателя type0 (для элемента 0), начиная с начала (index = 0) и type1 (для элемента 1), начиная с конца (index = array.length-1).
Инициализируйте type0 = 0 и type1 = array.length-1
2. Предполагается поместить 1 справа от массива. Как только это будет сделано, тогда 0 определенно будет в левой части массива.

C ++

// C ++ программа для сортировки
// двоичный массив за один проход
#include <bits/stdc++.h>

using namespace std;

  
/ * Функция для установки всех 0
слева и все 1 с справа * /

void segregate0and1(int arr[], 

                    int size)

{

    int type0 = 0;

    int type1 = size - 1;

      

    while(type0 < type1)

    {

        if(arr[type0] == 1)

        {

            swap(arr[type0], 

                 arr[type1]);

            type1--;

        }

        else

        type0++;

    }

}

  
// Код драйвера

int main()

{

    int arr[] = {0, 1, 0, 1, 1, 1};

    int i, arr_size = sizeof(arr) / 

                      sizeof(arr[0]);

  

    segregate0and1(arr, arr_size);

  

    cout << "Array after segregation is ";

    for (i = 0; i < arr_size; i++)

        cout << arr[i] << " ";

  

    return 0;

}

Джава

// Java-код для разделения 0 и 1

import java.util.*;

  

class GFG{

/**
Method for segregation 0 and 1 given input array
*/

static void segregate0and1(int arr[]) {

        int type0 = 0;

        int type1 = arr.length - 1;

          

        while (type0 < type1) {

            if (arr[type0] == 1) {

                // обмен

                arr[type1] = arr[type1]+ arr[type0];

                arr[type0] = arr[type1]-arr[type0];

                arr[type1] = arr[type1]-arr[type0];

                type1--;

            } else {

                type0++;

            }

        }

  

    }

      
// Драйвер программы

public static void main(String[] args) {     

          

        int[] array = {0, 1, 0, 1, 1, 1};

          

        segregate0and1(array);

          

        for(int a : array){

            System.out.print(a+" ");

        }

    }

}

Python 3

# Python программа для сортировки
# двоичный массив за один проход

  
# Функция поставить все 0 на
# слева и все 1 справа

def segregate0and1(arr, size):

  

    type0 = 0

    type1 = size - 1

      

    while(type0 < type1):

        if(arr[type0] == 1):

            (arr[type0], 

             arr[type1]) = (arr[type1],

                            arr[type0])

            type1 -= 1

        else:

            type0 += 1

      
Код водителя

arr = [0, 1, 0, 1, 1, 1]

arr_size = len(arr)

segregate0and1(arr, arr_size)

print("Array after segregation is"

                         end = " ")

for i in range(0, arr_size):

        print(arr[i], end = " ")

  
# Этот код добавлен
# by Shivi_Aggarwal

C #

// код C # для разделения 0 и 1

using System;

  

class GFG {

  
// Метод разделения 0
// и 1 заданный входной массив

static void segregate0and1(int[] arr)

{

    int type0 = 0;

    int type1 = arr.Length - 1;

  

    while (type0 < type1)

    {

        if (arr[type0] == 1)

        {

            // обмен

            arr[type1] = arr[type1] + arr[type0];

            arr[type0] = arr[type1] - arr[type0];

            arr[type1] = arr[type1] - arr[type0];

            type1--;

        }

          

        else

        {

            type0++;

        }

    }

  
}

  
// Код драйвера

public static void Main(string[] args)

{

  

    int[] array = new int[] {0, 1, 0, 1, 1, 1};

    segregate0and1(array);

  

    Console.Write("Array after segregation is ");

    foreach (int a in array)

    {

        Console.Write(a + " ");

    }

}
}

  
// Этот код предоставлен Shrikant13

PHP

<?php
// PHP программа для сортировки
// двоичный массив за один проход

  
// Функция для установки всех 0
// слева и все 1 с справа

function segregate0and1(&$arr , $size)

{

    $type0 = 0;

    $type1 = $size - 1;

      

    while($type0 < $type1)

    {

        if($arr[$type0] == 1)

        {

            $temp = $arr[$type0];

            $arr[$type0] = $arr[$type1];

            $arr[$type1] = $temp;

            $type1--;

        }

        else

        $type0++;

    }

}

  
// Код драйвера

$arr = array(0, 1, 0, 1, 1, 1);

$arr_size = sizeof($arr);

  

segregate0and1($arr, $arr_size);

  

echo ("Array after segregation is ");

for ($i = 0; $i < $arr_size; $i++)

    echo ($arr[$i] . " ");

  
// Этот код добавлен
// от Shivi_Aggarwal
?>

Выход:

Array after segregation is 0 0 1 1 1 1 

Временная сложность: O (n)

// Спасибо san4net за предложение этого метода.

Пожалуйста, напишите комментарии, если вы найдете какой-либо из приведенных выше алгоритмов / код неверным, или лучший способ решить ту же проблему.

Рекомендуемые посты:

Разделите 0 и 1 в массиве

0.00 (0%) 0 votes