Рубрики

Самый большой подмассив с равным числом 0 и 1

Для данного массива, содержащего только 0 и 1, найдите самый большой подмассив, который не содержит равных 0 и 1. Ожидаемая сложность времени O (n).

Примеры:

Input: arr[] = {1, 0, 1, 1, 1, 0, 0}
Output: 1 to 6 (Starting and Ending indexes of output subarray)

Input: arr[] = {1, 1, 1, 1}
Output: No such subarray

Input: arr[] = {0, 0, 1, 1, 0}
Output: 0 to 3 Or 1 to 4

Способ 1 (простой)
Простой способ — использовать два вложенных цикла. Внешний цикл выбирает начальную точку i. Внутренний цикл рассматривает все подмассивы, начиная с i. Если размер подмассива превышает максимальный размер, обновите максимальный размер.
В приведенном ниже коде 0 считаются как -1, и вычисляется сумма всех значений от i до j. Если сумма становится 0, то размер этого подмассива сравнивается с наибольшим размером.

C ++

// Простая программа на C ++ для поиска наибольшего подмассива
// с одинаковым количеством 0 и 1
#include<bits/stdc++.h> 

  

using namespace std; 

  
// Эта функция печатает начало и конец
// индексы наибольшего подмассива с равными
// число 0 и 1. И возвращает размер
// такого подмассива.

  

int findSubArray(int arr[], int n) 

    int sum = 0; 

    int maxsize = -1, startindex; 

  

    // Выберите начальную точку как я

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

    

        sum = (arr[i] == 0)? -1 : 1; 

  

        // Рассмотрим все подмассивы, начиная с i

        for (int j = i+1; j < n; j++) 

        

            (arr[j] == 0)? (sum += -1): (sum += 1); 

  

            // Если это подмассив с 0 суммой, то

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

            // рассчитано

            if (sum == 0 && maxsize < j-i+1) 

            

                maxsize = j - i + 1; 

                startindex = i; 

            

        

    

    if (maxsize == -1) 

        cout << "No such subarray"

    else

        cout << startindex << " to " << startindex + maxsize - 1; 

  

    return maxsize; 

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

int main() 

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

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

  

    findSubArray(arr, size); 

    return 0; 

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

С

// Простая программа для поиска наибольшего подмассива
// с одинаковым количеством 0 и 1

  
#include <stdio.h>

  
// Эта функция печатает начало и конец
// индексы наибольшего подмассива с равными
// число 0 и 1. И возвращает размер
// такого подмассива.

  

int findSubArray(int arr[], int n)

{

    int sum = 0;

    int maxsize = -1, startindex;

  

    // Выберите начальную точку как я

  

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

    {

        sum = (arr[i] == 0)? -1 : 1;

  

        // Рассмотрим все подмассивы, начиная с i

  

        for (int j = i+1; j < n; j++)

        {

            (arr[j] == 0)? (sum += -1): (sum += 1);

  

            // Если это подмассив с 0 суммой, то

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

            // рассчитано

  

            if (sum == 0 && maxsize < j-i+1)

            {

                maxsize = j - i + 1;

                startindex = i;

            }

        }

    }

    if (maxsize == -1)

        printf("No such subarray");

    else

        printf("%d to %d", startindex, startindex+maxsize-1);

  

    return maxsize;

}

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

  

int main()

{

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

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

  

    findSubArray(arr, size);

    return 0;

}

Джава

class LargestSubArray 

{

  

    // Эта функция печатает начало и конец

    // индексы наибольшего подмассива с равными

    // число 0 и 1. И возвращает размер

    // такого подмассива.

  

    int findSubArray(int arr[], int n) 

    {

        int sum = 0;

        int maxsize = -1, startindex = 0;

        int endindex = 0;

  

        // Выберите начальную точку как я

  

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

        {

            sum = (arr[i] == 0) ? -1 : 1;

  

            // Рассмотрим все подмассивы, начиная с i

  

            for (int j = i + 1; j < n; j++) 

            {

                if(arr[j] == 0)  

                    sum += -1

                else

                    sum += 1;

  

                // Если это подмассив с 0 суммой, то

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

                // рассчитано

  

                if (sum == 0 && maxsize < j - i + 1

                {

                    maxsize = j - i + 1;

                    startindex = i;

                }

            }

        }

        endindex = startindex+maxsize-1;

        if (maxsize == -1)

            System.out.println("No such subarray");

        else

            System.out.println(startindex+" to "+endindex);

  

        return maxsize;

    }

  

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

  

    public static void main(String[] args) 

    {

        LargestSubArray sub;

        sub = new LargestSubArray();

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

        int size = arr.length;

  

        sub.findSubArray(arr, size);

    }

}

python3

# Простая программа для поиска наибольшего подмассива
# с равным числом 0 и 1

  
# Эта функция печатает начало и конец
# индексы наибольшего подмассива с равными
# число 0 и 1. И возвращает размер
# такого подмассива.

def findSubArray(arr, n):

  

    sum = 0

    maxsize = -1

  

    # Выберите отправную точку, как я

  

    for i in range(0, n-1):

      

        sum = -1 if(arr[i] == 0) else 1

  

        # Рассмотрим все подмассивы, начиная с i

  

        for j in range(i + 1, n):

          

            sum = sum + (-1) if (arr[j] == 0) else sum + 1

  

            # Если это подмассив с 0 суммами, то

            # сравнить его с максимальным размером подмассива

            # рассчитано до сих пор

  

            if (sum == 0 and maxsize < j-i + 1):

                  

                maxsize = j - i + 1

                startindex = i

              

          

      

    if (maxsize == -1):

        print("No such subarray");

    else:

        print(startindex, "to", startindex + maxsize-1);

  

    return maxsize

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

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

size = len(arr)

findSubArray(arr, size)

  
# Этот код предоставлен Смитой Динеш Семвал

C #

// Простая программа для поиска наибольшего подмассива
// с одинаковым количеством 0 и 1

using System;

  

class GFG

{

              

    // Эта функция печатает начало и конец

    // индексы наибольшего подмассива с равными

    // число 0 и 1. И возвращает размер

    // такого подмассива.

  

    static int findSubArray(int []arr, int n) 

    {

        int sum = 0;

        int maxsize = -1, startindex = 0;

        int endindex = 0;

  

        // Выберите начальную точку как я

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

        {

            sum = (arr[i] == 0) ? -1 : 1;

  

            // Рассмотрим все подмассивы, начиная с i

  

            for (int j = i + 1; j < n; j++) 

            {

                if(arr[j] == 0) 

                    sum += -1; 

                else

                    sum += 1;

  

                // Если это подмассив с 0 суммой, то

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

                // рассчитано

  

                if (sum == 0 && maxsize < j - i + 1) 

                {

                    maxsize = j - i + 1;

                    startindex = i;

                }

            }

        }

        endindex = startindex+maxsize-1;

        if (maxsize == -1)

            Console.WriteLine("No such subarray");

        else

            Console.WriteLine(startindex+" to "+endindex);

  

        return maxsize;

    }

  

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

    public static void Main() 

    {

          

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

        int size = arr.Length;

        findSubArray(arr, size);

    }

}

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

PHP

<?php 
// Простая программа для поиска
// самый большой подмассив с равным
// число 0 и 1

  
// Эта функция печатает начальный
// и конечные индексы самого большого
// подрешетка с равным числом 0
// и 1с. Также возвращает размер
// такой подмассив.

function findSubArray(&$arr, $n)

{

    $sum = 0;

    $maxsize = -1;

  

    // Выберите начальную точку как я

  

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

    {

        $sum = ($arr[$i] == 0) ? -1 : 1;

  

        // Рассмотрим все подмассивы

        // начиная с меня

        for ($j = $i + 1; $j < $n; $j++)

        {

            ($arr[$j] == 0) ? 

               ($sum += -1) : ($sum += 1);

  

            // Если это подмассив с 0 суммой,

            // затем сравниваем это с максимумом

            // размер подмассива рассчитан до сих пор

  

            if ($sum == 0 && $maxsize < $j - $i + 1)

            {

                $maxsize = $j - $i + 1;

                $startindex = $i;

            }

        }

    }

    if ($maxsize == -1)

        echo "No such subarray";

    else

        echo $startindex. " to " .

            ($startindex + $maxsize - 1);

  

    return $maxsize;

}

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

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

$size = sizeof($arr);

  

findSubArray($arr, $size);

  
// Этот код предоставлен
// ChitraNayal
?>


Выход:

 0 to 5

Сложность времени: O (n ^ 2)
Вспомогательное пространство: O (1)

Метод 2 (хитрый)
Ниже приведено решение, которое использует O (n) дополнительного пространства и решает проблему за O (n) сложности времени.
Пусть входной массив будет arr [] размера n, а maxsize будет размером выходного подмассива.
1) Рассмотрим все 0 значений как -1. Теперь задача сводится к тому, чтобы определить максимальную длину подмассива с суммой = 0.
2) Создайте временный массив sumleft [] размера n. Сохраните сумму всех элементов от arr [0] до arr [i] в sumleft [i]. Это можно сделать за O (n) раз.
3) В двух случаях выходной подмассив может начинаться с 0-го индекса или может начинаться с некоторого другого индекса. Мы вернем максимум значений, полученных в двух случаях.
4) Чтобы найти подмассив максимальной длины, начиная с 0-го индекса, отсканируйте sumleft [] и найдите максимум i, где sumleft [i] = 0.
5) Теперь нам нужно найти подмассив, в котором сумма подмассива равна 0, а начальный индекс не равен 0. Эта проблема эквивалентна поиску двух индексов i & j в sumleft [], таких что sumleft [i] = sumleft [j] и ji это максимум. Чтобы решить эту проблему, мы можем создать хеш-таблицу с размером = max-min + 1, где min — минимальное значение в sumleft [], а max — максимальное значение в sumleft []. Идея состоит в том, чтобы хэшировать самые левые вхождения всех различных значений в sumleft []. Размер хэша выбирается как max-min + 1, потому что в sumleft может быть много разных возможных значений []. Инициализировать все значения в хэше как -1
6) Чтобы заполнить и использовать hash [], переместите sumleft [] от 0 до n-1. Если значение отсутствует в hash [], сохраните его индекс в hash. Если значение присутствует, то рассчитайте разницу текущего индекса sumleft [] и ранее сохраненного значения в hash []. Если эта разница больше, чем maxsize, обновите maxsize.
7) Для обработки угловых случаев (все 1 и все 0) мы инициализируем maxsize как -1. Если maxsize остается -1, то print нет такого подмассива.

С

// AO (n) программа для поиска наибольшего подмассива
// с одинаковым количеством 0 и 1

  
#include <stdio.h>
#include <stdlib.h>

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

  

int max(int a, int b) { return a>b? a: b; }

   
// Эта функция печатает начало и конец
// индексы наибольшего подмассива с равными
// число 0 и 1. И возвращает размер
// такого подмассива.

  

int findSubArray(int arr[], int n)

{

    // переменные для хранения значений результата

  

    int maxsize = -1, startindex;  

   

    // Создаем вспомогательный массив sunmleft [].

    // sumleft [i] будет суммой массива

    // элементы от arr [0] до arr [i]

  

    int sumleft[n];

  

    // Для значений min и max в sumleft []

  

    int min, max; 

    int i;

   

    // Заполняем массив sumleft и получаем min и max

    // значения в нем. Рассмотрим 0 значений в arr []

    // как -1

  

    sumleft[0] = ((arr[0] == 0)? -1: 1);

    min = arr[0]; max = arr[0];

    for (i=1; i<n; i++)

    {      

        sumleft[i] = sumleft[i-1] + ((arr[i] == 0)? 

                     -1: 1);

        if (sumleft[i] < min)

            min = sumleft[i];

        if (sumleft[i] > max)

            max = sumleft[i];

    }

   

    // Теперь вычисляем максимальное значение j - i, такое

    // это sumleft [i] = sumleft [j]. Идея

    // создать хеш-таблицу для хранения индексов всех

    // посещенные значения.

    // Если вы снова видите значение, это случай

    // sumleft [i] = sumleft [j]. Проверьте, если это джи

    // больше, чем maxsize.

    // Оптимальный размер хеша будет max-min + 1 как

    // эти много разных значений sumleft [i]

    // возможно. Так как мы используем оптимальный размер, нам нужно

    // сдвинуть все значения в sumleft [] на минуту раньше

    // используя их в качестве индекса в хеше [].

  

    int hash[max-min+1];

   

    // Инициализируем хеш-таблицу

  

    for (i=0; i<max-min+1; i++)

        hash[i] = -1;

   

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

    {

        // Случай 1: когда подмассив начинается с

        // индекс 0

  

        if (sumleft[i] == 0)

        {

           maxsize = i+1;

           startindex = 0;

        }

   

        // Случай 2: заполнить значение хеш-таблицы. Если уже

        // заполняем, затем используем

  

        if (hash[sumleft[i]-min] == -1)

            hash[sumleft[i]-min] = i;

        else

        {

            if ((i - hash[sumleft[i]-min]) > maxsize)

            {

                maxsize = i - hash[sumleft[i]-min];

                startindex = hash[sumleft[i]-min] + 1;

            }

        }

    }

    if (maxsize == -1)

        printf("No such subarray");

    else

        printf("%d to %d", startindex, startindex+maxsize-1);

   

    return maxsize;

}

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

int main()

{

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

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

   

    findSubArray(arr, size);

    return 0;

}

C ++ / STL

// C ++ программа для поиска наибольшего подмассива с равным количеством
// 0 и 1.

  
#include <bits/stdc++.h>

using namespace std;

  
// Возвращает самый большой подмассив с равным числом 0 и 1

  

int maxLen(int arr[], int n)

{

    // Создает пустой hashMap hM

  

    unordered_map<int, int> hM;

  

    int sum = 0;     // Инициализируем сумму элементов

    int max_len = 0; // Инициализировать результат

    int ending_index = -1;

  

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

        arr[i] = (arr[i] == 0)? -1: 1;

  

    // Пройти через данный массив

  

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

    {

        // Добавить текущий элемент в сумму

  

        sum += arr[i];

  

        // Для обработки sum = 0 в последнем индексе

  

        if (sum == 0)

        {

            max_len = i + 1;

            ending_index = i;

        }

  

        // Если эта сумма видна раньше, то обновляем max_len

        // если необходимо

  

        if (hM.find(sum + n) != hM.end())

        {

            if (max_len < i - hM[sum + n])

            {

                max_len = i - hM[sum + n];

                ending_index = i;

            }

        }

        else // Иначе положить эту сумму в хеш-таблицу

            hM[sum + n] = i;

    }

  

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

        arr[i] = (arr[i] == -1)? 0: 1;

  

    printf("%d to %d\n", ending_index-max_len+1, ending_index);

  

    return max_len;

}

  
// Метод драйвера

  

int main()

{

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

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

  

    maxLen(arr, n);

    return 0;

}

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

Джава

import java.util.HashMap;

  

class LargestSubArray1 

{

  

    // Возвращает самый большой подмассив с равным числом 0 и 1

   

    int maxLen(int arr[], int n) 

    {

        // Создает пустой hashMap hM

   

        HashMap<Integer, Integer> hM = new HashMap<Integer, Integer>();

  

        int sum = 0;     // Инициализируем сумму элементов

        int max_len = 0; // Инициализировать результат

        int ending_index = -1;

        int start_index = 0;

  

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

        {

            arr[i] = (arr[i] == 0) ? -1 : 1;

        }

  

        // Пройти через данный массив

   

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

        {

            // Добавить текущий элемент в сумму

   

            sum += arr[i];

  

            // Для обработки sum = 0 в последнем индексе

   

            if (sum == 0

            {

                max_len = i + 1;

                ending_index = i;

            }

  

            // Если эта сумма видна раньше, то обновляем max_len

            // если необходимо

   

            if (hM.containsKey(sum + n)) 

            {

                if (max_len < i - hM.get(sum + n)) 

                {

                    max_len = i - hM.get(sum + n);

                    ending_index = i;

                }

            

            else // Иначе положить эту сумму в хеш-таблицу

                hM.put(sum + n, i);

        }

  

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

        {

            arr[i] = (arr[i] == -1) ? 0 : 1;

        }

  

        int end = ending_index - max_len + 1;

        System.out.println(end + " to " + ending_index);

  

        return max_len;

    }

  

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

   

    public static void main(String[] args) 

    {

        LargestSubArray1 sub = new LargestSubArray1();

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

        int n = arr.length;

  

        sub.maxLen(arr, n);

    }

}

  
// Этот код был написан Mayank Jaiswal (mayank_24)

python3

# Python 3 программа для поиска крупнейших
# подмассив с равным количеством
# 0 и 1.

  
# Возвращает самый большой вложенный массив с
# равное количество 0 и 1

def maxLen(arr, n):

  

    # ПРИМЕЧАНИЕ: Dictonary в Python в

    # реализовано как Hash Maps.

    # Создать пустую хеш-карту (словарь)

    hash_map = {} ;

    curr_sum = 0

    max_len = 0

    ending_index = -1;

  

    for i in range (0, n):

        if(arr[i] == 0):

            arr[i] = -1;

        else:

            arr[i] = 1;

  

    # Пройти через данный массив

    for i in range (0, n):

      

        # Добавить текущий элемент в сумму

        curr_sum = curr_sum + arr[i];

  

        # Для обработки суммы = 0 в последнем индексе

        if (curr_sum == 0):

            max_len = i + 1;

            ending_index = i;

  

        # Если эта сумма видна раньше,

        # затем обновите max_len, если требуется

        if (curr_sum + n) in hash_map: 

            max_len = max(max_len, i -

                          hash_map[curr_sum + n]) 

        else

  

            # еще положить эту сумму в словарь

            hash_map[curr_sum] = i ;

          

    for i in range (0, n):

        if(arr[i] == -1):

            arr[i] = 0;

        else:

            arr[i] = 1;

              

    print (ending_index - max_len + 1,

                            end =" ");

    print ("to", end = " ");

    print (ending_index);

  

    return max_len;

  
Код водителя

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

n = len(arr) ;

  
maxLen(arr, n);

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

C #

// C # программа для поиска наибольшего подмассива
// с одинаковым количеством 0 и 1

using System;

using System.Collections.Generic;

  

class LargestSubArray1 {

  

    // Возвращает самый большой подмассив с

    // равное количество 0 и 1

    public virtual int maxLen(int[] arr, int n) {

          

        // Создаем пустой словарь hM

        Dictionary < int,

        int > hM = new Dictionary < int,

        int > ();

  

        int sum = 0; // Инициализируем сумму элементов

        int max_len = 0; // Инициализировать результат

        int ending_index = -1;

        int start_index = 0;

  

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

            arr[i] = (arr[i] == 0) ? -1 : 1;

        }

  

        // Пройти через данный массив

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

            // Добавить текущий элемент в сумму

            sum += arr[i];

  

            // Для обработки sum = 0 в последнем индексе

            if (sum == 0) {

                max_len = i + 1;

                ending_index = i;

            }

  

            // Если эта сумма видна раньше,

            // затем обновляем max_len

            // если необходимо

            if (hM.ContainsKey(sum + n)) {

                if (max_len < i - hM[sum + n]) {

                    max_len = i - hM[sum + n];

                    ending_index = i;

                }

            }

              

            else // Иначе положить эту сумму в хеш-таблицу

            {

                hM[sum + n] = i;

            }

        }

  

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

            arr[i] = (arr[i] == -1) ? 0 : 1;

        }

  

        int end = ending_index - max_len + 1;

        Console.WriteLine(end + " to " + ending_index);

  

        return max_len;

    }

  

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

public static void Main(string[] args) 

{

      

    LargestSubArray1 sub = new LargestSubArray1();

    int[] arr = new int[] 

    {

        1,

        0,

        0,

        1,

        0,

        1,

        1

    };

      

    int n = arr.Length;

    sub.maxLen(arr, n);

}
}

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

Выход:

 
0 to 5

Сложность времени: O (n)
Вспомогательное пространство: O (n)
Спасибо Aashish Barnwal за предложение этого решения.

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

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

Самый большой подмассив с равным числом 0 и 1

0.00 (0%) 0 votes