0と1の数が等しい最大のサブアレイ


難易度 ミディアム
よく聞かれる Amazon (アマゾン) 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の数は同じでした。

0秒カウント はこちらをご覧ください。⇒ 3

1秒カウント はこちらをご覧ください。⇒ 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. 次に、maxLengthの長さをマップから値i – map(sum + n)として更新し、endingIndexをiとして更新します。
    4. それ以外の場合は、その合計+ nをマップに入れます。
  5. endingIndex – maxLength +1およびendingIndexを出力します。

説明

配列が与えられ、0と1の数が等しい最大のサブ配列を見つけるように求められます。 同じ数の0と1を保持するすべてのサブ配列のすべての長さの中で最大になるように、サブ配列の範囲を見つけます。 を使用します ハッシュマップ を保管するため 整数 その中の値。 ハッシング 効率的なアプローチとより良い時間計算量を提供します。 値を取る 合計, 最大長 0として、コードで同時に更新します。 終了インデックスと呼ばれるXNUMXつの変数があります。これは、範囲の最後のポイントの値を保持します。これは、サブ配列の終了範囲の最大長である必要があります。

配列をトラバースして、配列の値のいずれかが0に等しいかどうかを確認し、それを-1としてマークし、1を保持する配列値をそのままにします。 ここでは実際の範囲を見つけるつもりはないからです。 論理は、ゼロと0の数が等しく、長さの範囲が偶数であることを意味するものを数えることです。 したがって、1を-0としてマークし、配列内に値を追加します。 合計が1であることがわかった場合、それは、等しい1と0のペアが0つ見つかったことを意味します。これは、各1を-XNUMXとしてマークしたため、すべての-XNUMXとXNUMXが合計としてXNUMXになるため、それを数えることができます。

要約すると、配列内のすべての値を合計し、それが0に等しいかどうかを調べます。等しい場合は、配列のmaxLengthと配列のendingIndexを更新するだけです。 sum + nがまだ存在しない場合はマップに配置し、存在する場合はいくつかの条件を確認してから、maxLengthとendingIndexの値を更新します。 範囲の開始点としてendingIndex– maxLength + 1を出力し、範囲の終了点としてendingIndexを出力します。

0と1の数が等しい最大のサブアレイ

コード

0と1の数が等しい最大のサブ配列を見つけるためのC ++コード

#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

0と1の数が等しい最大のサブ配列を見つけるためのJavaでの実装

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) where 「n」 配列内の要素の数です。 ここでは、HashMapを使用しているため、O(n)でこの問題を解決できます。 HashMapは、O(1)時間計算量の要素を挿入、削除、または変更できるためです。

スペースの複雑さ

O(N) where 「n」 配列内の要素の数です。 最悪の場合にハッシュマップに挿入される要素の数は最大でnになるためです。 この線形空間の複雑さが達成されます。