1의 개수가 0의 개수보다 하나 더 많은 가장 긴 부분 배열

난이도 쉽게
자주 묻는 질문 Accenture 아마존 드 쇼 삼성
배열 해시조회수 24

우리는 정렬 정수 배열에는 1과 0 만 포함됩니다. 문제 설명은 1의 숫자가있는 가장 긴 하위 배열의 길이가 하위 배열의 0 개수보다 하나 더 많은 것을 알아 내도록 요청합니다.

입력:

arr [] = {1,0,1,1,0,0,0}

출력:

5

설명 :

0부터 4까지의 인덱스, {1, 0, 1, 1, 0}, XNUMX 개 1과 0 개의 XNUMX. 1보다 0이 한 번 더 있습니다.

입력:

arr [] = {1,0,1,0,0}

출력:

3

설명 :

0에서 2까지의 인덱스, {1, 0, 1}에는 1 개의 0과 1 개의 0이 있습니다. XNUMX보다 XNUMX이 한 번 더 있습니다.

암호알고리즘

  1. 지도를 선언하십시오.
  2. sum 및 outputLength를 0으로 설정합니다.
  3. i = 0에서 i <n까지 배열을 횡단합니다.
    1. 참이면 arr [i]가 0인지 확인하고 합계에 -1을 더합니다.
    2. 그렇지 않으면 합계에 +1을 더합니다.
    3. 확인 합계는 같다 1로 설정 한 다음 outputLength 값을 1 씩 늘립니다.
    4. 그렇지 않으면지도에 합계가 참이면 합계가 포함되어 있지 않은지 확인한 다음 합계와 함께 i의 합계와 현재 값을지도에 입력합니다.
    5. 지도에 (sum-1)이 포함되어 있는지 확인하십시오.
    6. outputLength가 i-index (지도의 합계 값)보다 작은 경우.
      1. true이면 outputLength를 i-index로 업데이트합니다.
  4. 출력 길이를 반환합니다.

설명

우리는 지도. 해당 맵에서 조건이 충족되면 합계의 값과 인덱스의 현재 값을 저장합니다. 두 개의 변수를 가져 와서 sum을 0으로 설정하고 outputLength를 0으로 설정합니다. 배열을 순회하는 동안 배열의 각 요소를 선택하고 arr [i]가 0과 같은지 확인하고 동일하다고 확인되면 추가합니다. -1을 사용하여 합계하고 합계에 저장합니다. 그렇지 않으면 0이 아닌 경우 양수 1을 합계에 더하고 합계에 저장합니다.

그 음수 1과 양수 1 뒤에있는 이유는 우리는 모두 0을 -1로 가장하고 1로 더하기 때문에 항상 0을 얻습니다. 그러나 우리는 합에서 양수 1을 검사 할 것입니다. 이는 우리가 하나의 추가 1과 0의 개수를 가질 것임을 나타냅니다.

1을 -0로 가장하면 1, 0, 1을 취하고 처음 0 개의 숫자로 2을 얻고 세 번째 숫자로 조건이 충족되었음을 알 수 있습니다. 1보다 0의 추가 카운트가있는 1과 0의 하위 배열을 얻었습니다. 조건이 충족됩니다. 그래서 알고리즘의 다음 단계에서 합계가 1인지 찾고 outputLength의 길이를 업데이트 할 것입니다. 마지막으로 if 문에서 새 출력 길이를 얻으면 이전 출력 길이를 현재 outputLength로 업데이트해야하며 outputLength를 반환합니다.

실시

1의 개수가 0 개수보다 하나 더 많은 가장 긴 하위 배열에 대한 C ++ 프로그램

#include <iostream>
#include<unordered_map>

using namespace std;

int getLongestLen(int arr[], int n)
{
    unordered_map<int, int> MAP;
    int sum = 0, outputLength= 0;

    for (int i = 0; i < n; i++)
    {

        if(arr[i] == 0)
            sum += -1;
        else
            sum += 1;


        if (sum == 1)
        {
            outputLength = i + 1;
        }
        else if (MAP.find(sum) == MAP.end())
        {
            MAP[sum] = i;
        }

        if (MAP.find(sum - 1) != MAP.end())
        {
            if (outputLength < (i - MAP[sum - 1]))
                outputLength = i - MAP[sum - 1];
        }
    }
    return outputLength;
}
int main()
{
    int arr[] = {1,0,1,1,0,0,0};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Length of the longest Sub-Array : "<<getLongestLen(arr, n);
    return 0;
}
Length of the longest Sub-Array : 5

1의 개수가 0 개수보다 하나 더 많은 가장 긴 하위 배열을위한 Java 프로그램

import java.util.HashMap;

class longestSubArray01
{
    public static int getLongestLen(int arr[], int n)
    {
        HashMap<Integer, Integer> MAP = new HashMap<Integer,Integer>();
        int sum = 0, outputLength = 0;

        for (int i = 0; i < n; i++)
        {
            if(arr[i] == 0)
                sum += -1;
            else
                sum += 1;

            if (sum == 1)
                outputLength = i + 1;
            else if (!MAP.containsKey(sum))
                MAP. put(sum, i);


            if (MAP.containsKey(sum - 1))
            {
                if (outputLength < (i - MAP.get(sum - 1)))
                    outputLength = i - MAP.get(sum - 1);
            }
        }
        return outputLength;
    }
    public static void main(String[] args)
    {
        int arr[] = {1,0,1,1,0,0,0};
        int n = arr.length;
        System.out.println("Length of the longest Sub-Array : " +getLongestLen(arr, n));
    }
}
Length of the longest Sub-Array : 5

1 개수가 0 개수보다 하나 더 많은 가장 긴 부분 배열에 대한 복잡성 분석

시간 복잡성

O (N) 어디에 "엔"  배열의 요소 수입니다.

공간 복잡성

O (N) 어디에 "엔"  배열의 요소 수입니다.

Translate »