Найдите первый "недостающий" номер в отсортированном списке

Ответ 1

Использовать двоичный поиск. Если диапазон чисел не имеет отверстия, то разница между окончанием и началом диапазона также будет количеством записей в диапазоне.

Таким образом, вы можете начать со всего списка чисел и отрубить первую или вторую половину, исходя из того, имеет ли первая половина пробел. В конце концов вы попадете в диапазон с двумя записями с отверстием посередине.

Сложность этого времени O(log N). Контраст с линейным сканированием, худшим случаем которого является O(N).

Ответ 2

На основе подхода, предложенного выше @phs, здесь приведен код C:

#include <stdio.h>

int find_missing_number(int arr[], int len) {
    int first, middle, last;
    first = 0;
    last = len - 1;
    middle = (first + last)/2;

    while (first < last) {
        if ((arr[middle] - arr[first]) != (middle - first)) {
            /* there is a hole in the first half */
            if ((middle - first) == 1 && (arr[middle] - arr[first] > 1)) {
                return (arr[middle] - 1);
            }

            last = middle;
        } else if ((arr[last] - arr[middle]) != (last - middle)) {
            /* there is a hole in the second half */
            if ((last - middle) == 1 && (arr[last] - arr[middle] > 1)) {
                return (arr[middle] + 1);
            }

            first = middle;
        } else {
            /* there is no hole */
            return -1;
        }

        middle = (first + last)/2;
    }

    /* there is no hole */
    return -1;
}

int main() {
    int arr[] = {3, 5, 1};
    printf("%d", find_missing_number(arr, sizeof arr/(sizeof arr[0]))); /* prints 4 */
    return 0;
}

Ответ 3

Так как числа от 0 до n - 1 сортируются в массиве, первые числа должны быть такими же, как и их индексы. Это означает, что число 0 находится в ячейке с индексом 0, номер 1 находится в ячейке с индексом 1 и так далее. Если недостающее число обозначается как m. Числа меньше m расположены в ячейках с индексами, такими же, как значения.

Число m + 1 находится в ячейке с индексом m. Число m + 2 расположено в ячейке с индексом m + 1 и т.д. Мы видим, что недостающее число m является первой ячейкой, значение которой не совпадает с ее значением.

Следовательно, требуется искать в массиве, чтобы найти первую ячейку, значение которой не совпадает с ее значением. Поскольку массив отсортирован, мы можем найти его в O (lg n) времени на основе алгоритма бинарного поиска, как показано ниже:

int getOnceNumber_sorted(int[] numbers)
{
    int length = numbers.length
    int left = 0;
    int right = length - 1;
    while(left <= right)
    {
        int middle = (right + left) >> 1;
        if(numbers[middle] != middle)
        {
            if(middle == 0 || numbers[middle - 1] == middle - 1)
                return middle;
            right = middle - 1;
        }
        else
            left = middle + 1;
    }


    return -1;
}

Это решение заимствовано из моего блога: http://codercareer.blogspot.com/2013/02/no-37-missing-number-in-array.html.

Ответ 4

На основе алгоритма, предоставленного @phs

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

    if(end<=start+1){
        return start+1;
    }
    else{

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

        if((array[mid] - array[start]) != (mid-start))
            return findFirstMissing(array, start, mid);
        else
            return findFirstMissing(array, mid+1, end);

    }
}

Ответ 5

Вы считали кодировку длины пробега? То есть вы кодируете первое число, а также количество чисел, которые следуют за ним последовательно. Вы не только можете представить числа, используемые очень эффективно таким образом, первое отверстие будет в конце первого сегмента кодированной длины.

Чтобы проиллюстрировать ваш пример:

[0, 1, 2, 4, 6]

Будет закодирован как:

[0:3, 4:1, 6:1]

Где x: y означает, что существует набор чисел, последовательно начинающийся с x для y чисел в строке. Это немедленно говорит нам, что первый пробел находится в местоположении 3. Обратите внимание, однако, что это будет намного более эффективно, когда назначенные адреса группируются вместе, а не распределены случайным образом по всему диапазону.

Ответ 6

если список отсортирован, я буду перебирать список и делать что-то вроде этого кода на Python:

missing = []
check = 0
for n in numbers:
    if n > check:
        # all the numbers in [check, n) were not present
        missing += range(check, n)
    check = n + 1

# now we account for any missing numbers after the last element of numbers
if check < MAX:
    missing += range(check, MAX + 1)

если количество чисел отсутствует, возможно, вы захотите использовать предложение кодировки длины @Nathan для списка missing.

Ответ 7

Array: [1,2,3,4,5,6,8,9]
Index: [0,1,2,3,4,5,6,7]


int findMissingEmementIndex(int a[], int start, int end)
{
    int mid = (start + end)/2;

    if( Math.abs(a[mid] - a[start]) != Math.abs(mid - start) ){

        if(  Math.abs(mid - start) == 1 && Math.abs(a[mid] - a[start])!=1 ){
            return start +1; 
        }
        else{
            return findMissingElmementIndex(a,start,mid);
        }

    }
    else if( a[mid] - a[end] != end - start){

        if(  Math.abs(end - mid) ==1 && Math.abs(a[end] - a[mid])!=1 ){
           return mid +1; 
        }
        else{
            return findMissingElmementIndex(a,mid,end);
        }
    }
    else{
        return No_Problem;
    }
}

Ответ 8

У меня есть один алгоритм поиска недостающего числа в отсортированном списке. его сложность - logN.

        public int execute2(int[] array) {
        int diff = Math.min(array[1]-array[0], array[2]-array[1]);
        int min = 0, max = arr.length-1;
        boolean missingNum = true;
        while(min<max) {
            int mid = (min + max) >>> 1;
            int leftDiff = array[mid] - array[min];
            if(leftDiff > diff * (mid - min)) {
                if(mid-min == 1)
                    return (array[mid] + array[min])/2;
                max = mid;
                missingNum = false;
                continue;
            }
            int rightDiff = array[max] - array[mid];
            if(rightDiff > diff * (max - mid)) {
                if(max-mid == 1)
                    return (array[max] + array[mid])/2;
                min = mid;
                missingNum = false;
                continue;
            }
            if(missingNum)
                break;
        }
        return -1;
    }

Ответ 9

На основе алгоритма, предоставленного @phs

    public class Solution {
      public int missing(int[] array) {
        // write your solution here
        if(array == null){
          return -1;
        }
        if (array.length == 0) {
          return 1;
        }
        int left = 0;
        int right = array.length -1;
        while (left < right - 1) {
          int mid = left + (right - left) / 2;
          if (array[mid] - array[left] != mid - left) { //there is gap in [left, mid]
            right = mid;
          }else if (array[right] - array[mid] != right - mid) { //there is gap in [mid, right]
            left = mid;
          }else{ //there is no gapin [left, right], which means the missing num is the at 0 and N
            return array[0] == 1 ? array.length + 1 : 1 ;
          }

        }
        if (array[right] - array[left] == 2){ //missing number is between array[left] and array[right]
          return left + 2;
        }else{
          return array[0] == 1 ? -1 : 1; //when ther is only one element in array
        }

      }
    }

Ответ 10

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

Алгоритм в коде C

int missingNumber(int a[], int size) {
    int lo = 0;
    int hi = size - 1; 

    // TODO: Use this if we need to ensure we start at 0!
    //if(a[0] != 0) { return 0; }

    // All elements present? If so, return next largest number.
    if((hi-lo) == (a[hi]-a[lo])) { return a[hi]+1; }

    // While 2 or more elements to left to consider...
    while((hi-lo) >= 2) { 
        int mid = (lo + hi) / 2;
        if((mid-lo) != (a[mid]-a[lo])) {  // Explore left-hand side
            hi = mid;
        } else {  // Explore right hand side
            lo = mid + 1;
        }
    }

    // Return missing value from the two candidates remaining...
    return (lo == (a[lo]-a[0])) ? hi + a[0] : lo + a[0];
}

Тестируемые выходы

    int a[] = {0};  // Returns: 1
    int a[] = {1};  // Returns: 2

    int a[] = {0, 1};  // Returns: 2
    int a[] = {1, 2};  // Returns: 3
    int a[] = {0, 2};  // Returns: 1

    int a[] = {0, 2, 3, 4};  // Returns: 1
    int a[] = {0, 1, 2, 4};  // Returns: 3

    int a[] = {0, 1, 2, 4, 5, 6, 7, 8, 9};  // Returns: 3
    int a[] = {2, 3, 5, 6, 7, 8, 9};        // Returns: 4
    int a[] = {2, 3, 4, 5, 6, 8, 9};        // Returns: 7

    int a[] = {-3, -2, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9};      // Returns: -1
    int a[] = {-3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9};  // Returns: 10

Общая процедура:

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

Примечание. Предположениями алгоритма являются:

• Первый и последний элементы считаются никогда не пропущенными. Эти элементы устанавливают диапазон.
• В массиве отсутствует только одно целое число. Это не найдет больше одного недостающего целого!
• Ожидается, что целое число в массиве будет увеличиваться с шагом 1, а не с любой другой скоростью.

Ответ 11

Отсутствует

Number=(1/2)(n)(n+1)-(Sum of all elements in the array)

Здесь n - размер array+1.