最大数目等于0和1的子数组  


难度级别 中等
经常问 亚马逊 Coursera GreyOrange MakeMyTrip 摩根士丹利 Paytm 新思 时代互联网
排列 哈希

您将得到一个整数数组。 输入数组中的整数仅为0和1。 问题陈述要求找出最大的子数组,该子数组可以具有等于0和1的相等计数。

使用案列  

arr[]={0,1,0,1,0,1,1,1}
0 to 5 (total 6 elements)

说明

从数组位置0到5,不等于0和1

0s计数 3

1s计数 ⇒ 3

这是最大的子数组,不包含0和1。

查找数目相等的0和1的最大子数组的算法  

  1. 声明一个 哈希图.
  2. 总和, 最长长度, 起始索引 到0和 结尾索引 至-1。
  3. 遍历数组并将数组的每个元素更新为-1(如果等于0)。
  4. 从0到n-1(n是数组的长度)的起始循环。
    1. 将arr [i]的每个值相加。
    2. 检查总和是否等于0,如果为true,
      1. 然后更新 最长长度 作为i + 1,并且 结尾索引 和我一样
    3. 检查地图中是否包含sum + n,
      1. 然后,将map的maxLength的长度更新为值i – map(sum + n),而endIndex则更新为i。
    4. 否则,将那个总和+ n放入地图中。
  5. 打印EndingIndex – maxLength + 1和EndingIndex。

说明  

给定一个数组,我们被要求找出数目相等的0和1的最大子数组。 找到子数组的范围,使其在所有子数组的所有长度中都应该是最大的,并且所有子数组的长度相等,分别为0和1。 我们将使用 哈希图 用于存储 整数 值。 哈希 提供了一种有效的方法和更好的时间复杂度。 取值 总和, 最长长度 为0,那么我们将在代码中同时更新它。 我们将有一个名为EndingIndex的变量,该变量将保存范围的最后一个点的值,其中该点应该是子数组结束范围的最大长度。

参见
树遍历(预购,订购和后订购)

遍历该数组,以查找该数组的任何值是否等于0,那么我们将其标记为-1,并保留原样保留1的数组值。 因为这里我们不会找出实际范围。 逻辑是计数等于零的零和一的数字,表示偶数长度范围。 因此,当我们将值添加到数组中时,我们会将0标记为-1。 如果我们发现总和为0,则意味着我们找到了一对相等的1和1,因为自-0和0标记为-1以来,每个-XNUMX和XNUMX都将XNUMX作为总和,因此我们可以对其进行计数。

我们要总结一个数组中的每个值,并找出它是否等于0,如果相等,则只需更新数组的maxLength和数组的endingIndex。 我们将把sum + n放入映射中(如果尚不存在),如果存在,则检查某些条件,然后更新maxLength和endingIndex的值。 打印EndingIndex – maxLength +1作为范围的起点,而EndingIndex作为范围的终点。

最大数目等于0和1的子数组

代码  

C ++代码查找相等数目的0和1的最大子数组

#include<iostream>
#include<unordered_map>

using namespace std;

int getLargestSubA(int arr[], int n)
{
    unordered_map<int, int> MAP;

    int sum = 0;
    int maxLength = 0;
    int endingIndex = -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];
        if (sum == 0)
        {
            maxLength = i + 1;
            endingIndex = i;
        }
        if (MAP.find(sum + n) != MAP.end())
        {
            if (maxLength < i - MAP[sum + n])
            {
                maxLength = i - MAP[sum + n];
                endingIndex = i;
            }
        }
        else
            MAP[sum + n] = i;
    }
    cout<<endingIndex - maxLength + 1 <<" to " <<endingIndex;

    return maxLength;
}

int main()
{
    int arr[] = { 0,1,0,1,0,1,1,1 };
    int n = sizeof(arr) / sizeof(arr[0]);

    getLargestSubA(arr, n);
    return 0;
}
0 to 5

用Java实现以找到最大个数相等的0和1子数组

import java.util.HashMap;

class LargestSubArrayWithEqual01
{
    public static int getLargestSubA(int arr[], int n)
    {
        HashMap<Integer, Integer> MAP = new HashMap<Integer, Integer>();

        int sum = 0;

        int maxLength = 0;
        int endingIndex = -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];
            if (sum == 0)
            {
                maxLength = i + 1;
                endingIndex = i;
            }
            if (MAP.containsKey(sum + n))
            {
                if (maxLength < i - MAP.get(sum + n))
                {
                    maxLength = i - MAP.get(sum + n);
                    endingIndex = i;
                }
            }
            else
                MAP.put(sum + n, i);

        }
        int end = endingIndex - maxLength + 1;
        System.out.println(end + " to " + endingIndex);

        return maxLength;
    }
    
    public static void main(String[] args)
    {
        int arr[] = {0,1,0,1,0,1,1,1};
        int n = arr.length;

        getLargestSubA(arr, n);
    }
}
0 to 5

复杂度分析  

时间复杂度

O(N) 哪里 “ n” 是数组中元素的数量。 在这里,因为我们使用了HashMap,所以可以在O(n)中解决此问题。 因为HashMap可以以O(1)时间复杂度插入,删除或修改元素。

参见
删除链接列表元素Leetcode解决方案

空间复杂度

O(N) 哪里 “ n” 是数组中元素的数量。 由于将在最坏的情况下插入到哈希图中的元素数量最多为n。 实现了这种线性空间复杂性。