동일한 수의 0과 1을 가진 가장 큰 부분 배열


난이도 중급
자주 묻는 질문 아마존 Coursera 그레이 오렌지 MakeMyTrip 모건 스탠리 (Morgan Stanley) Paytm Synopsys 타임즈 인터넷
배열 해시

정수 배열이 제공됩니다. 정수는 입력 배열에서 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인지 확인하고 참이면
      1. 그런 다음 업데이트 최대 길이 i + 1 및 엔딩 인덱스 i.
    3. 지도에 sum + n이 포함되어 있는지 확인하십시오.
      1. 그런 다음 maxLength의 길이를 맵에서 i – map (sum + n) 값으로 업데이트하고 endingIndex를 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로 표시했기 때문에 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) 어디에 "엔" 배열의 요소 수입니다. 여기서 우리는 HashMap을 사용했기 때문에 O (n)에서이 문제를 해결할 수 있습니다. HashMap은 O (1) 시간 복잡도의 요소를 삽입, 삭제 또는 수정할 수 있기 때문입니다.

공간 복잡성

O (N) 어디에 "엔" 배열의 요소 수입니다. 최악의 경우 해시 맵에 삽입되는 요소의 수는 최대 n 개이기 때문입니다. 이 선형 공간 복잡성이 달성됩니다.