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

정수 배열이 제공됩니다. 정수는 입력 배열에서 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을 가진 가장 큰 부분 배열을 찾는 알고리즘

선언 해시맵.
세트 합, 최대 길이, 시작 인덱스 0 및 엔딩 인덱스 -1로.
배열을 탐색하고 1과 같으면 배열의 각 요소를 -0로 업데이트합니다.
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을지도에 넣습니다.
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이있는 가장 큰 부분 배열을 찾는 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 개이기 때문입니다. 이 선형 공간 복잡성이 달성됩니다.

Twitter Facebook 링크드 인 버퍼 레딧 텀블러