algorithm - 在排序列表中查找第一个“缺失”数字

Question

假设我有整数的连续范围[0, 1, 2, 4, 6]，其中3是第一个“缺失”的数字。我需要一个算法来找到第一个“洞”。由于范围非常大（可能包含2^32条目），因此效率很重要。数字范围存储在磁盘上；空间效率也是一个主要问题。

什么是最佳的时间和空间效率算法？

score 40 · Accepted Answer

使用二分查找。如果一个数字范围没有漏洞，那么该范围的结束和开始之间的差异也将是该范围内的条目数。

因此，您可以从整个数字列表开始，然后根据前半部分是否有差距来截断前半部分或后半部分。最终你会来到一个有两个入口的范围，中间有一个洞。

这个的时间复杂度是O(log N)。与线性扫描相比，最坏的情况是O(N).

score 6 · Accepted Answer

根据上面@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;
}

score 4 · Accepted Answer

由于从 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。

score 3 · Accepted Answer

基于@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);

    }
}

score 3 · Accepted Answer

下面是我的解决方案，我认为它很简单，并且避免了过多令人困惑的 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 的步长增加，而不是以任何其他速率增加。

score 1 · Accepted Answer

您是否考虑过运行长度编码？也就是说，您对第一个数字以及连续跟随它的数字的计数进行编码。您不仅可以通过这种方式非常有效地表示使用的数字，而且第一个孔将位于第一个行程编码段的末尾。

用你的例子来说明：

[0, 1, 2, 4, 6]

将被编码为：

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

其中 x:y 表示有一组数字从 x 开始连续 y 个数字。这立即告诉我们第一个间隙位于位置 3。但是请注意，当分配的地址聚集在一起而不是随机分散在整个范围内时，这将更加有效。

score 0 · Accepted Answer

如果列表已排序，我将遍历列表并执行类似以下 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。

score 0 · Accepted Answer

0

失踪

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

这里n是的大小array+1。

于 2012-11-18T18:49:06.400 回答

score 0 · Accepted Answer

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;
    }
}

score 0 · Accepted Answer

这是一个面试题。我们将有一个包含多个缺失数字的数组，我们会将所有这些缺失的数字放在一个 ArrayList 中。

public class Test4 {
    public static void main(String[] args) {
        int[] a = { 1, 3, 5, 7, 10 };
        List<Integer> list = new ArrayList<>();

        int start = 0;
        for (int i = 0; i < a.length; i++) {
            int ch = a[i];
            if (start == ch) {
                start++;
            } else {
                list.add(start);
                start++;
                i--; // a must do.
            } // else
        } // for
        System.out.println(list);

    }

}

score 0 · Accepted Answer

函数式编程解决方案 (Scala)

漂亮优雅

懒惰的评价

def gapFinder(sortedList: List[Int], start: Int = 0): Int = {
  def withGuards: Stream[Int] =
    (start - 1) +: sortedList.toStream :+ (sortedList.last + 2)

  if (sortedList.isEmpty) start
  else withGuards.sliding(2)
  .dropWhile { p => p.head + 1 >= p.last }.next()
  .headOption.getOrElse(start) + 1
} // 8-line solution

// Tests
assert(gapFinder(List()) == 0)
assert(gapFinder(List[Int](0)) == 1)
assert(gapFinder(List[Int](1)) == 0)
assert(gapFinder(List[Int](2)) == 0)
assert(gapFinder(List[Int](0, 1, 2)) == 3)
assert(gapFinder(List[Int](0, 2, 4)) == 1)
assert(gapFinder(List[Int](0, 1, 2, 4)) == 3)
assert(gapFinder(List[Int](0, 1, 2, 4, 5)) == 3)

score 0 · Accepted Answer

import java.util.Scanner;
class MissingNumber {
  public static void main(String[] args) {

    Scanner scan = new Scanner(System.in);
    int n = scan.nextInt();
    int[] arr =new int[n];
    for (int i=0;i<n;i++){
      arr[i]=scan.nextInt();
    }
    for (int i=0;i<n;i++){
      if(arr[i+1]==arr[i]+1){

      }
      else{
        System.out.println(arr[i]+1);
        break;
      }
    }

  }
}

score 0 · Accepted Answer

我正在寻找一种超级简单的方法来在 javascript 中找到具有最大潜在值的排序数组中的第一个缺失数字，并且不必太担心效率，因为我不打算使用更长的列表 10-20最多的项目。这是我想出的递归函数：

  function findFirstMissingNumber(sortedList, index, x, maxAllowedValue){
    if(sortedList[index] == x && x < maxAllowedValue){
      return findFirstMissingNumber(sortedList, (index+1), (x+1), maxAllowedValue);
    }else{ return x; }
  }

  findFirstMissingNumber([3, 4, 5, 7, 8, 9], 0, 3, 10);
  //expected output: 6

给它你的数组，你希望开始的索引，你期望它的值和你想要检查的最大值。

score -1 · Accepted Answer

我有一种算法可以在排序列表中找到丢失的数字。它的复杂度是 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;
    }

score -1 · Accepted Answer

基于@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
        }

      }
    }

score -1 · Accepted Answer

public static int findFirst(int[] arr) {
    int l = -1;
    int r = arr.length;
    while (r - l > 1) {
        int middle = (r + l) / 2;
        if (arr[middle] > middle) {
            r = middle;
        }
        l = middle;
    }
    return r;
}

algorithm - 在排序列表中查找第一个“缺失”数字

16 回答 16

C代码中的算法

测试输出

Related

Reference