연속 배열


난이도 중급
자주 묻는 질문 아마존 MakeMyTrip 모건 스탠리 (Morgan Stanley) Paytm
해싱 슬라이딩 윈도우

주어진 정렬 숫자 0과 1로만 구성됩니다. o와 1로 똑같이 구성된 가장 긴 연속 하위 배열의 길이를 찾아야합니다.

입력

arr = [0,1,0,1,0,0,1]

산출

6

설명

가장 긴 연속적인 하위 배열 빨간색 [0,1,0,1,0,0,1] 길이는 6입니다.

암호알고리즘

  1. maxlen 값을 0으로 설정합니다.
  2. 두 개의 루프를 사용합니다. 첫 번째 루프에서 zer_count를 0으로, one_count를 0으로 설정합니다.
  3. 값이 특정 인덱스에 배열 0이면 zero_count를 1 씩 늘립니다.
  4. 그렇지 않으면 업데이트하고 one_count를 1 씩 늘립니다.
  5. 각 반복에서 zero_count가 one_count와 같은지 확인하고 같으면 (maxlen 및 j-i + 1) 사이에 더 큰 번호를 찾습니다.
  6. maxlen 반환

설명

우리의 주요 아이디어는 XNUMX과 XNUMX 만있는 가장 긴 연속 하위 배열의 길이를 찾는 것이므로 우리의 주요 초점은 그 길이를 찾는 것입니다.

따라서 중첩 for 루프를 사용합니다. 외부 루프에서 우리는 zero_count 및 one_count 값을 0으로 초기화합니다. 왜냐하면 내부 루프에서 나올 때마다 모든 반복 후에는 모든 것을 다시 확인하기 위해 zero_count와 one_count의 새로운 값이 필요하기 때문입니다. 배열의 길이에 도달 할 때까지 루프를 반복합니다.

이제 배열의 모든 단일 값을 확인합니다. arr [index]의 값이 0 또는 1이면 0과 같은 값이 있으면 zero_count의 값을 1 씩 업데이트하고 늘리거나 arr [index]의 값을 늘립니다. 1로 확인되면 one_count 값을 1 씩 업데이트하고 증가시킵니다.

이제 다음 if 블록은 zero_count가 one_count와 같은지 확인하고 같으면 maxlen과 j-i + 1 사이에서 더 큰 숫자를 찾아서 maxlen에 더 큰 숫자를 저장합니다.

주어진 배열을 가정합니다. arr [] = {1,0,0,1,0,1,0}

zero_count = 0, one_count = 0, maxlen = 0

i = 0에서 => j = i

j = 0

arr [j]에서 0과 같지 않으면 one_count ++는 one_count = 1을 의미합니다.

j = 1

arr [j]가 0이면 zero_count ++는 zero_count = 1을 의미합니다.

이 자리에서 다음에 블록이 실행되면 maxlen과 j-i + 1 사이에 더 큰 no를주고 maxlen에서 2를 반환합니다.

j = 2

arr [j]가 0이면 zero_count ++는 zero_count = 2을 의미합니다.

j = 3

arr [j]가 0이 아니면 one_count ++는 one_count = 2를 의미합니다.

이 자리에서 다음에 블록이 실행되면 maxlen과 j-i + 1 사이에 더 큰 no를주고 maxlen에서 4를 반환합니다.

j = 4

arr [j]가 0이면 zero_count ++는 zero_count = 3을 의미합니다.

j = 5

arr [j]가 0이 아니면 one_count ++는 one_count = 3를 의미합니다.

이 자리에서 다음에 블록이 실행되면 maxlen과 j-i + 1 사이에 더 큰 no를주고 maxlen에서 6를 반환합니다.

j = 6

arr [j]가 0이면 zero_count ++는 zero_count = 4을 의미합니다.

그리고 모든 조건이 실패 할 때까지 루프를 계속 반복합니다.

그리고 maxlen을 6으로 반환합니다.

실시

연속 배열을위한 C ++ 프로그램

#include <iostream>
using namespace std;
int contiguous_Array(int arr[], int n)
{
    int i,j,maxlen=0;
    for( i = 0 ; i < n ; i++)
    {
        int zero_count=0,one_count=0;
        for(j = i ; j < n ; j++)
        {
            if( arr[j] == 0 )
            {
                zero_count++;
            }
            else
            {
                one_count++;
            }
            if(zero_count==one_count)
            {
                maxlen=std::max(maxlen,j-i+1);
            }
        }
    }
    return maxlen;
}
int main()
{
    int arr[]= {1,0,0,1,0,1,0};
    int n=sizeof(arr)/sizeof(arr[0]);
    cout <<contiguous_Array(arr,n)<< endl;
    return 0;
}
6

연속 배열 용 Java 프로그램

public class Contiguous_Array {

  public static int solution(int[] arr) {

    int maxlen = 0;

    for (int i = 0; i<arr.length; i++) {

      int zero_count = 0, one_count = 0;

      for (int j = i; j<arr.length; j++) {

        if (arr[j] == 0) {
          zero_count++;
        } else {
          one_count++;
        }
        if (zero_count == one_count) {

          maxlen = Math.max(maxlen, j - i + 1);

        }
      }
    }
    return maxlen;
  }
  public static void main(String args[]) {

    int[] arr = new int[] {
      0, 1, 0, 1, 0, 0, 1
    };

    System.out.println(solution(arr));

  }
}
6

연속 배열에 대한 복잡성 분석

시간 복잡성

O (N * N) 어디에 N 주어진 배열의 크기입니다.

공간 복잡성

O (1) 여기에 여분의 공간을 사용하지 않기 때문입니다.

참고