查找要翻轉的零,以使連續的1的數量最大化


難度級別 容易獎學金
經常問 ol石 亞馬遜 GE醫療集團 信息邊緣 百會
排列

問題陳述

在“查找零位以使連續的1的個數最大化”問題中,我們給出了一個二進制數 排列 和一個數字x代表編號。 的零被翻轉。 編寫程序以查找需要翻轉的零,以使連續1的_number最大化。

輸入格式

第一行也是只有一行包含整數值n。

第二行包含n個數字(0或1),以空格分隔。

包含整數x的第三行表示要翻轉的零的數量。

輸出格式

用空格隔開打印x個整數,表示我們將零翻轉的位置的索引。

約束

  • 1 <= n <= 10 ^ 5
  • 0 <= a [i] <= 1
  • 1 <= x <= n

7
0 1 0 1 1 0 1
2
2 5

說明: 在上面的示例中,我們可以看到索引2和5的零被翻轉了。 我們獲得了最大數量的連任。

算法

在這種方法中,主要思想是使用滑動窗口概念。

1. 初始化變量計數以跟踪零個數

2. 直到窗口的右指針小於輸入數組

3. 如果計數小於輸入的零,則向右增加窗口大小,如果發現任何零,則增加計數值。

4. 如果計數大於輸入的零,則從左側減小窗口大小,如果發現任何零,則使計數值遞減。

5. 如果窗口大小大於先前的窗口大小,則將其作為最佳窗口。

6. 在最佳窗口中打印零索引。

履行

C ++程序查找要翻轉的零,以使連續的1的數目最大化

#include<bits/stdc++.h> 
using namespace std; 


int main() 
{ 
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    int x;
    cin>>x;
    int left = 0, right = 0; 
  int temp = 0, ans = 0; 
  int count=0; 
  while(right<n) 
  { 
    if(count <= x) 
    { 
      if (a[right] == 0) 
      count++; 
      right++; 
    } 
    if(count>x) 
    { 
      if(a[left] == 0) 
      count--; 
      left++; 
    } 
    if ((right-left > ans) && (count<=x)) 
    { 
      ans = right-left; 
      temp = left; 
    } 
  } 
  for(int i=0;i<ans; i++) 
  { 
    if(a[temp+i]==0) 
    {
        cout<<temp+i<< " ";
    }
  } 
return 0; 
} 

Java程序查找要翻轉的零,以使連續的1的數目最大化

import java.util.Scanner;
class sum
{
    public static void main(String[] args)
    {
        Scanner sr = new Scanner(System.in);
        int n=sr.nextInt();
        int a[]= new int[n];
        for(int i=0;i<n;i++)
        {
            a[i]=sr.nextInt();
        }
        int x = sr.nextInt();
        int left = 0, right = 0; 
  int temp = 0, ans = 0; 
  int count=0; 
  while(right<n) 
  { 
    if(count <= x) 
    { 
      if (a[right] == 0) 
      count++; 
      right++; 
    } 
    if(count>x) 
    { 
      if(a[left] == 0) 
      count--; 
      left++; 
    } 
    if ((right-left > ans) && (count<=x)) 
    { 
      ans = right-left; 
      temp = left; 
    } 
  } 
  for(int i=0;i<ans; i++) 
  { 
    if(a[temp+i]==0) 
    {
        System.out.print((temp+i) + " ");
    }
  } 
    }
}
6
1 0 0 1 0 1
1
4

複雜度分析

時間複雜度

O(N) 哪裡 n 是給定數組的大小 一種[]。 在這裡,我們使用滑動窗口的概念,它需要線性時間。

空間複雜度

O(1) 因為我們在這裡沒有定義任何輔助空間。