連續數組  


難度級別 中烘焙
經常問 亞馬遜 我的旅行 摩根士丹利(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

解釋  

我們的主要思想是找到最長的連續子數組的長度,該子數組只有零和一個,因此,我們的主要重點是找到該長度。

因此,我們將使用嵌套的for循環。 在外循環中,我們將zero_count和one_count的值初始化為0,因為在每次迭代從內循環出來後,我們都需要新的zero_count和one_count值來再次檢查所有值。 我們將遍歷循環,直到達到數組的長度為止。

也可以看看
在給定範圍內對數組進行三向分區

現在,它將檢查數組的每個單個值,如果arr [index]的值為0或1,如果它的值等於0,則將1_count的值更新並增加1,或者將arr [index]的值增加1如果發現為XNUMX,則將one_count的值更新並增加XNUMX。

現在,下一個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之間給出更大的否,並在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之間給出更大的否,並在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之間給出更大的否,並在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) 因為我們在這裡不使用任何多餘的空間。

參考文獻