Рубрики

Найдите наименьшее пропущенное число

Дан отсортированный массив из n различных целых чисел, где каждое целое находится в диапазоне от 0 до m-1 и m> n. Найдите наименьшее число, которое отсутствует в массиве.

Примеры
Ввод: {0, 1, 2, 6, 9}, n = 5, m = 10
Выход: 3

Ввод: {4, 5, 10, 11}, n = 4, m = 12
Выход: 0

Ввод: {0, 1, 2, 3}, n = 4, m = 5
Выход: 4

Ввод: {0, 1, 2, 3, 4, 5, 6, 7, 10}, n = 9, m = 11
Выход: 8

Спасибо Равичандре за предложение следующих двух методов.

Способ 1 (использовать бинарный поиск)
Для i = 0 до m-1 выполните бинарный поиск i в массиве. Если я не присутствую в массиве, вернем i.

Сложность времени: O (m log n)

Метод 2 (линейный поиск)
Если arr [0] не равно 0, вернуть 0. В противном случае пройти через входной массив, начиная с индекса 0, и для каждой пары элементов a [i] и a [i + 1] найти разницу между ними. если разница больше 1, то a [i] +1 — отсутствующее число.

Сложность времени: O (n)

Метод 3 (использовать модифицированный бинарный поиск)
Благодаря yasein и замятия, предложившего этот метод.
В стандартном процессе двоичного поиска искомый элемент сравнивается со средним элементом, и на основе результата сравнения мы решаем, закончен ли поиск или перейти к левой или правой половине.
В этом методе мы модифицируем стандартный алгоритм бинарного поиска, чтобы сравнить средний элемент с его индексом и принять решение на основе этого сравнения.

… 1) Если первый элемент не совпадает с его индексом, вернуть первый индекс
… 2) Иначе получить средний индекс, скажем, средний
………… а) Если arr [mid] больше, чем mid, то требуемый элемент находится в левой половине.
………… б) Иначе необходимый элемент лежит в правой половине.

C ++

// C ++ программа для поиска мельчайших элементов
// отсутствует в отсортированном массиве.
#include<bits/stdc++.h>

using namespace std;

  

int findFirstMissing(int array[], 

                    int start, int end)

{

    if (start > end)

        return end + 1;

  

    if (start != array[start])

        return start;

  

    int mid = (start + end) / 2;

  

    // Левая половина имеет все элементы

    // от 0 до середины

    if (array[mid] == mid)

        return findFirstMissing(array, 

                            mid+1, end);

  

    return findFirstMissing(array, start, mid);

}

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

int main()

{

    int arr[] = {0, 1, 2, 3, 4, 5, 6, 7, 10};

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

    cout << "Smallest missing element is " <<

        findFirstMissing(arr, 0, n-1) << endl;

}

  
// Этот код предоставлен
// Shivi_Aggarwal

С

// Программа на C, чтобы найти самые маленькие элементы, отсутствующие
// в отсортированном массиве.
#include<stdio.h>

  

int findFirstMissing(int array[], int start, int end)

{

    if (start  > end)

        return end + 1;

  

    if (start != array[start])

        return start;

  

    int mid = (start + end) / 2;

  

    // Левая половина имеет все элементы от 0 до середины

    if (array[mid] == mid)

        return findFirstMissing(array, mid+1, end);

  

    return findFirstMissing(array, start, mid);

}

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

int main()

{

    int arr[] = {0, 1, 2, 3, 4, 5, 6, 7, 10};

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

    printf("Smallest missing element is %d",

           findFirstMissing(arr, 0, n-1));

    return 0;

}

Джава

class SmallestMissing 

{

    int findFirstMissing(int array[], int start, int end) 

    {

        if (start > end)

            return end + 1;

  

        if (start != array[start])

            return start;

  

        int mid = (start + end) / 2;

  

        // Левая половина имеет все элементы от 0 до середины

        if (array[mid] == mid)

            return findFirstMissing(array, mid+1, end);

  

        return findFirstMissing(array, start, mid);

    }

  

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

    public static void main(String[] args) 

    {

        SmallestMissing small = new SmallestMissing();

        int arr[] = {0, 1, 2, 3, 4, 5, 6, 7, 10};

        int n = arr.length;

        System.out.println("First Missing element is : "

                + small.findFirstMissing(arr, 0, n - 1));

    }

}

python3

# Python3 программа для поиска самых маленьких
# элементов, отсутствующих в отсортированном массиве.

  

def findFirstMissing(array, start, end):

  

    if (start > end):

        return end + 1

  

    if (start != array[start]):

        return start;

  

    mid = int((start + end) / 2)

  

    # Левая половина имеет все элементы

    # от 0 до середины

    if (array[mid] == mid):

        return findFirstMissing(array,

                          mid+1, end)

  

    return findFirstMissing(array, 

                          start, mid)

  

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

arr = [0, 1, 2, 3, 4, 5, 6, 7, 10]

n = len(arr)

print("Smallest missing element is",

      findFirstMissing(arr, 0, n-1))

  
# Этот код предоставлен Смитой Динеш Семвал

C #

// C # программа для поиска самых маленьких
// элементы отсутствуют в отсортированном массиве.

using System;

  

class GFG

{

    static int findFirstMissing(int []array,

                            int start, int end) 

    {

        if (start > end)

            return end + 1;

  

        if (start != array[start])

            return start;

  

        int mid = (start + end) / 2;

  

        // Левая половина имеет все элементы от 0 до середины

        if (array[mid] == mid)

            return findFirstMissing(array, mid+1, end);

  

        return findFirstMissing(array, start, mid);

    }

  

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

    public static void Main() 

    {

        int []arr = {0, 1, 2, 3, 4, 5, 6, 7, 10};

        int n = arr.Length;

          

        Console.Write("smallest Missing element is : "

                    + findFirstMissing(arr, 0, n - 1));

    }

}

  
// Этот код предоставлен Sam007

PHP

<?php
// PHP программа для поиска
// самые маленькие элементы отсутствуют
// в отсортированном массиве.

  
// функция, которая возвращает
// самые маленькие элементы отсутствуют
// в отсортированном массиве.

function findFirstMissing($array, $start, $end)

{

    if ($start > $end)

        return $end + 1;

  

    if ($start != $array[$start])

        return $start;

  

    $mid = ($start + $end) / 2;

  

    // Левая половина имеет все

    // элементы от 0 до середины

    if ($array[$mid] == $mid)

        return findFirstMissing($array

                                $mid + 1, 

                                $end);

  

    return findFirstMissing($array

                            $start

                            $mid);

}

  

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

    $arr = array (0, 1, 2, 3, 4, 5, 6, 7, 10);

    $n = count($arr);

    echo "Smallest missing element is " ,

          findFirstMissing($arr, 2, $n - 1);

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

Выход:

Smallest missing element is 8

Примечание. Этот метод не работает, если в массиве есть повторяющиеся элементы.

Сложность времени: O (Logn)

Пожалуйста, напишите комментарии, если вы обнаружите, что приведенные выше коды / алгоритмы неверны, или найдете другие способы решения той же проблемы.

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

Найдите наименьшее пропущенное число

0.00 (0%) 0 votes