最大數目等於0和1的子數組  


難度級別 中烘焙
經常問 亞馬遜 Coursera 灰色橙色 我的旅行 摩根士丹利(Morgan Stanley) 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。 實現了這種線性空間複雜性。