Подсчет подмассивов с равным количеством единиц и нулей


Сложный уровень Легко
Часто спрашивают в Cisco Купон Coursera Databricks карат SAP Labs Тесла
массив Hash

Постановка задачи

Задача «Подсчитать подмассивы с равным количеством единиц и нулей» утверждает, что вам дан массив, состоящий только из нулей и единиц. В постановке задачи предлагается определить количество подмассивов, состоящих не из 1 и не из 0.

Пример

arr[] = {0, 0, 1, 1, 0}
4

Пояснение: Все подмассивы: (1,2), (3,4), (0,3), (1,4)

Подсчет подмассивов с равным количеством единиц и нулей

 

arr[] = {1,0,0,1,1,0}
7

Пояснение: Все подмассивы: (0, 1), (2,3), (0,3), (1,4), (0,5), (4,5), (2,5).

Алгоритм

1. Declare the map.
2. Set the output and sum to 0.
3. Traverse the array, while i<n.
  1. Set arr[i] = -1, if arr[i] is equal to 0.
  2. Add the value of arr[i] to the sum.
  3. If the sum is equal to 0, then increase the value of output by 1.
  4. If the map contains the sum, then add the output to the frequency of the current sum’s value in the map.
  5. If the map contains the value sum, then just increase the frequency of the previous sum’s frequency in the map by 1.
  6. Else put that new sum and marks its frequency as 1.
4. Return output.

объяснение

Мы дали массив, состоящий только из нулей и единиц. Итак, нам нужно узнать количество подмассивов, которые содержат только 0 и 1. Мы собираемся использовать хеширования. Мы объявим карта. На карте мы собираемся сохранить сумму и ее частоту как 1. Если это новое значение для карты, добавьте его на карту, иначе увеличьте частоту предыдущего значения суммы, присутствующего на карте.

Но перед этим мы будем преобразовывать все 0 в -1 при обходе цикла. Если мы нашли элемент массива как 0, мы будем преобразовывать его в -1. Добавление значения текущего элемента массива к сумме. Проверим сумму, если сумма равна 0, мы будем увеличивать значение выпуска. Это потому, что мы конвертируем все 0 в -1, а у нас есть только 1 и 0. Итак, когда мы конвертируем 0 в -1 и добавляем это значение с 1 с. Всякий раз, когда сумма равна 0, это возможно только тогда, когда у нас есть равные 0 и 1.

Предположим, у нас есть три единицы и три нуля, и преобразовав каждый 1 в -0 и сложив три единицы и три -0, мы получим 1 в качестве суммы. Это также означает, что после преобразования 1 в -1, чтобы получить 0 в качестве суммы, мы должны иметь равные 0 и 1. Поэтому, когда вы найдете значение суммы как 0, мы увеличим выходное значение. Учитывая входной массив, мы будем обновлять значение вывода всякий раз, когда получим сумму как 0.

Код:

Код C ++ для подсчета подмассивов с равным количеством единиц и нулей

#include <iostream>
#include<map>

using namespace std;

int getSubArrayWithEqual01(int arr[], int n)
{
    map<int,int> MAP;
    int sum=0;
    int output=0;
    for (int i = 0; i < n; i++)
    {
        if (arr[i] == 0)
            arr[i] = -1;

        sum += arr[i];

        if (sum == 0)
            output++;

        if (MAP[sum])
            output += MAP[sum];

        if(MAP[sum]==0)
            MAP[sum]=1;
        else
            MAP[sum]++;
    }
    return output;
}
int main()
{
    int arr[] = { 0, 0, 1, 1, 0};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout<<"Sub-Arrays with equal 0's and 1's count is: " <<getSubArrayWithEqual01(arr, n);
}
Sub-Arrays with equal 0's and 1's count is: 4

Код Java для подсчета подмассивов с равным количеством единиц и нулей

import java.util.HashMap;
class SubArrayCount01
{
    public static int getSubArrayWithEqual01(int[] arr, int n)
    {
        HashMap<Integer, Integer> MAP = new HashMap<>();
        int sum = 0;
        int output = 0;
        for (int i = 0; i < n; i++)
        {
            if (arr[i] == 0)
            {
                arr[i] = -1;
            }
            sum += arr[i];

            if (sum == 0)
            {
                output++;
            }
            if (MAP.containsKey(sum))
                output += MAP.get(sum);

            if (!MAP.containsKey(sum))
            {
                MAP.put(sum, 1);
            }
            else
            {
                MAP.put(sum, MAP.get(sum) + 1);
            }
        }
        return output;
    }
    public static void main(String[] args)
    {
        int arr[] = { 0, 0, 1, 1, 0 };
        int n = arr.length;
        System.out.println("Sub-Arrays with equal 0's and 1's count is:" +getSubArrayWithEqual01(arr, n));
    }
}
Sub-Arrays with equal 0's and 1's count is:4

Анализ сложности

Время C0mplexity

О (п) в котором «Н» - количество элементов в массиве. Поскольку мы использовали HashMap, мы можем достичь линейной временной сложности.

Космическая сложность

О (п) в котором «Н» - количество элементов в массиве. Здесь, в HashMap, мы сохранили сумму как ключ, таким образом достигается линейная пространственная сложность.