Рубрики

Найти недостающий номер в отсортированном массиве

Дан список из n-1 целых чисел, и эти целые числа находятся в диапазоне от 1 до n. В списке нет дубликатов. Одно из целых чисел отсутствует в списке. Напишите эффективный код, чтобы найти пропущенное целое число.

Примеры:

Input : arr[] = [1, 2, 3, 4, 6, 7, 8]
Output : 5

Input : arr[] = [1, 2, 3, 4, 5, 6, 8, 9]
Output : 7

Одно простое решение — применить обсуждаемые методы для поиска отсутствующего элемента в несортированном массиве . Временная сложность этого решения составляет O (n).

Эффективное решение основано на алгоритме «разделяй и властвуй», который мы видели в бинарном поиске. Концепция этого решения состоит в том, что элементы, появляющиеся перед отсутствующим элементом, будут иметь ar [i] — i = 1, а элементы, появляющиеся после отсутствующего элемента будет иметь ar [i] — i = 2.

Это решение имеет временную сложность O (log n)

C ++

// Программа на основе бинарного поиска, чтобы найти
// единственное пропущенное число в отсортированном массиве
// отдельные элементы в ограниченном диапазоне.
#include <iostream>

using namespace std;

  

int search(int ar[], int size)

{

    int a = 0, b = size - 1;

    int mid;

    while ((b - a) > 1) {

        mid = (a + b) / 2;

        if ((ar[a] - a) != (ar[mid] - mid))

            b = mid;

        else if ((ar[b] - b) != (ar[mid] - mid))

            a = mid;

    }

    return (ar[mid] + 1);

}

  

int main()

{

    int ar[] = { 1, 2, 3, 4, 5, 6, 8 };

    int size = sizeof(ar) / sizeof(ar[0]);

    cout << "Missing number:" << search(ar, size);

}

Джава

// Программа на основе бинарного поиска
// найти единственное пропущенное число
// в отсортированном массиве различных
// элементы в ограниченном диапазоне.

import java.io.*;

  

class GFG 

{

static int search(int ar[], 

                  int size)

{

    int a = 0, b = size - 1;

    int mid = 0;

    while ((b - a) > 1)

    {

        mid = (a + b) / 2;

        if ((ar[a] - a) != (ar[mid] - mid))

            b = mid;

        else if ((ar[b] - b) != (ar[mid] - mid))

            a = mid;

    }

    return (ar[mid] + 1);

}

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

public static void main (String[] args) 

{

    int ar[] = { 1, 2, 3, 4, 5, 6, 8 };

    int size = ar.length;

    System.out.println("Missing number: " +

                        search(ar, size));

}
}

  
// Этот код добавлен
// по inder_verma.

python3

# Программа для бинарного поиска, чтобы найти
# единственное пропущенное число в отсортированном
# в отсортированном массиве отдельных элементов
# в ограниченном диапазоне

def search(ar, size):

    a = 0

    b = size - 1

    mid = 0

    while b > a + 1:

        mid = (a + b) // 2

        if (ar[a] - a) != (ar[mid] - mid):

            b = mid

        elif (ar[b] - b) != (ar[mid] - mid):

            a = mid

    return ar[mid] + 1

  
Код водителя

a = [1, 2, 3, 4, 5, 6, 8]

n = len(a)

  

print("Missing number:", search(a, n))

  
# Этот код добавлен
# Мохит Кумар

C #

// Программа на основе бинарного поиска
// найти единственное пропущенное число
// в отсортированном массиве различных
// элементы в ограниченном диапазоне.

using System;

  

class GFG 

{

static int search(int []ar, 

                  int size)

{

    int a = 0, b = size - 1;

    int mid = 0;

    while ((b - a) > 1)

    {

        mid = (a + b) / 2;

        if ((ar[a] - a) != (ar[mid] - mid))

            b = mid;

        else if ((ar[b] - b) != (ar[mid] - mid))

            a = mid;

    }

    return (ar[mid] + 1);

}

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

static public void Main (String []args) 

{

    int []ar = { 1, 2, 3, 4, 5, 6, 8 };

    int size = ar.Length;

    Console.WriteLine("Missing number: " +

                        search(ar, size));

}
}

  
// Этот код добавлен
// Арнаб Кунду

PHP

<?php
// Программа на основе бинарного поиска, чтобы найти
// единственное пропущенное число в отсортированном массиве
// отдельные элементы в ограниченном диапазоне.

  

function search($ar, $size)

{

    $a = 0;

    $b = $size - 1;

    $mid;

    while (($b - $a) > 1)

    {

        $mid = (int)(($a + $b) / 2);

        if (($ar[$a] - $a) != ($ar[$mid] - 

                                   $mid))

            $b = $mid;

        else if (($ar[$b] - $b) != ($ar[$mid] - 

                                        $mid))

            $a = $mid;

    }

    return ($ar[$mid] + 1);

}

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

$ar = array(1, 2, 3, 4, 5, 6, 8 );

$size = sizeof($ar);

echo "Missing number: "

     search($ar, $size);

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


Выход:

Missing number: 7

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

Найти недостающий номер в отсортированном массиве

0.00 (0%) 0 votes