Рубрики

Найти индекс 0, который нужно заменить на 1, чтобы получить самую длинную непрерывную последовательность 1 с в двоичном массиве

Учитывая массив 0s и 1s, найдите позицию 0, которая будет заменена на 1, чтобы получить самую длинную непрерывную последовательность 1s. Ожидаемая сложность по времени составляет O (n), а вспомогательное пространство — O (1).
Пример:

Input: 
   arr[] =  {1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1}
Output:
  Index 9
Assuming array index starts from 0, replacing 0 with 1 at index 9 causes
the maximum continuous sequence of 1s.

Input: 
   arr[] =  {1, 1, 1, 1, 0}
Output:
  Index 4

Мы настоятельно рекомендуем свернуть браузер и попробовать это в первую очередь.

Простое решение состоит в том, чтобы пройти массив, для каждого 0, посчитать число 1 с обеих сторон от него. Следите за максимальным количеством для любого 0. Наконец, верните индекс 0 с максимальным числом 1 с вокруг него. Временная сложность этого решения составляет O (n 2 ).

Используя эффективное решение , проблема может быть решена за время O (n). Идея состоит в том, чтобы отслеживать три индекса: текущий индекс ( curr ), предыдущий нулевой индекс ( prev_zero ) и предыдущий предыдущий нулевой индекс ( prev_prev_zero ). Пройдя по массиву, если текущий элемент равен 0, вычислите разницу между curr и prev_prev_zero (эта разница минус единица равна числу 1 с вокруг prev_zero). Если разница между curr и prev_prev_zero больше максимальной, обновите максимальную. Наконец, верните индекс prev_zero с максимальной разницей.

Ниже приведены реализации вышеуказанного алгоритма.

C ++

// C ++ программа для поиска индекса 0, который нужно заменить на 1, чтобы получить
// самая длинная непрерывная последовательность 1 с в двоичном массиве
#include<iostream>

using namespace std;

  
// Возвращает индекс 0 для замены на 1, чтобы получить самый длинный
// непрерывная последовательность 1 с. Если в массиве нет 0, то
// возвращает -1.

int maxOnesIndex(bool arr[], int n)

{

    int max_count = 0;  // для максимального числа 1 вокруг нуля

    int max_index;  // для сохранения результата

    int prev_zero = -1;  // индекс предыдущего нуля

    int prev_prev_zero = -1; // индекс предыдущего до предыдущего нуля

  

    // Обход входного массива

    for (int curr=0; curr<n; ++curr)

    {

        // Если текущий элемент равен 0, тогда вычисляем разницу

        // между curr и prev_prev_zero

        if (arr[curr] == 0)

        {

            // Обновить результат, если счетчик 1 вокруг prev_zero больше

            if (curr - prev_prev_zero > max_count)

            {

                max_count = curr - prev_prev_zero;

                max_index = prev_zero;

            }

  

            // Обновление для следующей итерации

            prev_prev_zero = prev_zero;

            prev_zero = curr;

        }

    }

  

    // Проверка на последний найденный ноль

    if (n-prev_prev_zero > max_count)

       max_index = prev_zero;

  

    return max_index;

}

  
// Драйвер программы

int main()

{

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

    int n = sizeof(arr)/sizeof(arr[0]);

    cout << "Index of 0 to be replaced is "

         << maxOnesIndex(arr, n);

    return 0;

}

Джава

// Java-программа для поиска индекса 0, который нужно заменить на 1, чтобы получить
// самая длинная непрерывная последовательность 1 с в двоичном массиве

  

import java.io.*;

  

class Binary 

{    

    // Возвращает индекс 0 для замены на 1, чтобы получить самый длинный

    // непрерывная последовательность 1 с. Если в массиве нет 0, то

    // возвращает -1.

    static int maxOnesIndex(int arr[], int n)

    {

        int max_count = 0// для максимального числа 1 вокруг нуля

        int max_index=0// для сохранения результата

        int prev_zero = -1// индекс предыдущего нуля

        int prev_prev_zero = -1; // индекс предыдущего до предыдущего нуля

   

        // Обход входного массива

        for (int curr=0; curr<n; ++curr)

        {

            // Если текущий элемент равен 0, тогда вычисляем разницу

            // между curr и prev_prev_zero

            if (arr[curr] == 0)

            {

                // Обновить результат, если счетчик 1 вокруг prev_zero больше

                if (curr - prev_prev_zero > max_count)

                {

                    max_count = curr - prev_prev_zero;

                    max_index = prev_zero;

                }

   

                // Обновление для следующей итерации

                prev_prev_zero = prev_zero;

                prev_zero = curr;

            }

        }

   

        // Проверка на последний найденный ноль

        if (n-prev_prev_zero > max_count)

            max_index = prev_zero;

   

        return max_index;

    }

      

      

    // Программа драйвера для проверки вышеуказанной функции

    public static void main(String[] args)

    {

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

        int n = arr.length;

        System.out.println("Index of 0 to be replaced is "

                           maxOnesIndex(arr, n));        

    }

}
/ * Этот код предоставлен Девешом Агравалом * /

python3

# Python программа для поиска индекса
# из 0 будет заменено на 1, чтобы получить
# самая длинная непрерывная последовательность
количество единиц в двоичном массиве

  
# Возвращает индекс 0, чтобы быть
# заменяется на 1, чтобы получить самый длинный
# непрерывная последовательность 1 с.
# Если в массиве нет 0, то
# возвращает -1.

def maxOnesIndex(arr,n):

      

    # для максимального числа от 1 до нуля

    max_count = 0

  

    # для сохранения результата

    max_index =0  

  

    # индекс предыдущего нуля

    prev_zero = -1  

  

    # индекс предыдущего до предыдущего нуля

    prev_prev_zero = -1 

   

    # Обход входного массива

    for curr in range(n):

      

        # Если текущий элемент равен 0,

        # тогда посчитайте разницу

        # между curr и prev_prev_zero

        if (arr[curr] == 0):

          

            # Обновить результат, если количество

            # 1s вокруг prev_zero больше

            if (curr - prev_prev_zero > max_count):

              

                max_count = curr - prev_prev_zero

                max_index = prev_zero

              

   

            # Обновление для следующей итерации

            prev_prev_zero = prev_zero

            prev_zero = curr

   

    # Проверить последний найденный ноль

    if (n-prev_prev_zero > max_count):

        max_index = prev_zero

   

    return max_index

   
# Драйверная программа

  

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

n = len(arr)

  

print("Index of 0 to be replaced is ",

    maxOnesIndex(arr, n))

  
# Этот код добавлен
# Анант Агарвал.

C #

// C # программа для поиска индекса 0 для замены
// с 1, чтобы получить самую длинную непрерывную последовательность
// 1 в двоичном массиве

using System;

  

class GFG {

      

    // Возвращает индекс 0 для замены на

    // 1, чтобы получить самую длинную непрерывную последовательность

    // 1с. Если в массиве нет 0, то это

    // возвращает -1.

    static int maxOnesIndex(int []arr, int n)

    {

          

        // для максимального числа 1 вокруг нуля

        int max_count = 0; 

          

        // для сохранения результата

        int max_index = 0; 

          

        // индекс предыдущего нуля

        int prev_zero = -1; 

          

        // индекс предыдущего до предыдущего нуля

        int prev_prev_zero = -1; 

  

        // Обход входного массива

        for (int curr = 0; curr < n; ++curr)

        {

              

            // Если текущий элемент равен 0, то

            // вычисляем разницу

            // между curr и prev_prev_zero

            if (arr[curr] == 0)

            {

                  

                // Обновить результат, если счет 1с

                // вокруг prev_zero больше

                if (curr - prev_prev_zero > max_count)

                {

                    max_count = curr - prev_prev_zero;

                    max_index = prev_zero;

                }

  

                // Обновление для следующей итерации

                prev_prev_zero = prev_zero;

                prev_zero = curr;

            }

        }

  

        // Проверка на последний найденный ноль

        if (n-prev_prev_zero > max_count)

            max_index = prev_zero;

  

        return max_index;

    }

      

    // Программа драйвера для проверки вышеуказанной функции

    public static void Main()

    {

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

                                     0, 1, 1, 1};

        int n = arr.Length;

    Console.Write("Index of 0 to be replaced is "

                         + maxOnesIndex(arr, n));     

    }

}

  
// Этот код предоставлен нитин митталь.

PHP

<?php
// PHP программа для поиска индекса 0
// заменяется на 1, чтобы получить самый длинный непрерывный
// последовательность 1 с в двоичном массиве

  
// Возвращает индекс 0 для замены на
// 1, чтобы получить самую длинную непрерывную последовательность из 1 с.
// Если в массиве нет 0, то он возвращает -1.

function maxOnesIndex( $arr, $n)

{

    $max_count = 0; // для максимального количества

                    // 1 вокруг нуля

    $max_index; // для сохранения результата

    $prev_zero = -1; // индекс предыдущего нуля

    $prev_prev_zero = -1; // индекс предыдущего к

                          // предыдущий ноль

  

    // Обход входного массива

    for ($curr = 0; $curr < $n; ++$curr)

    {

        // Если текущий элемент равен 0, то

        // вычисляем разницу

        // между curr и prev_prev_zero

        if ($arr[$curr] == 0)

        {

            // Обновить результат, если счет 1с

            // вокруг prev_zero больше

            if ($curr - $prev_prev_zero > $max_count)

            {

                $max_count = $curr - $prev_prev_zero;

                $max_index = $prev_zero;

            }

  

            // Обновление для следующей итерации

            $prev_prev_zero = $prev_zero;

            $prev_zero = $curr;

        }

    }

  

    // Проверка на последний найденный ноль

    if ($n - $prev_prev_zero > $max_count)

    $max_index = $prev_zero;

  

    return $max_index;

}

  
// Код драйвера

$arr = array(1, 1, 0, 0, 1, 0, 1, 

             1, 1, 0, 1, 1, 1);

$n = sizeof($arr);

echo "Index of 0 to be replaced is ",

      maxOnesIndex($arr, $n);

  
// Этот код предоставлен ajit
?>


Выход:

Index of 0 to be replaced is 9

Сложность времени: O (n)
Вспомогательное пространство: O (1)

Эта статья предоставлена Анкур Сингхом . Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Найти индекс 0, который нужно заменить на 1, чтобы получить самую длинную непрерывную последовательность 1 с в двоичном массиве

0.00 (0%) 0 votes