用高效的算法从数组中获取丢失的数字？？[重复]

Question

我正在做以下编程练习：Number Zoo Patrol。声明是：

背景：

你在一个数字动物园工作，似乎有一个数字不见了！

动物园的工作人员不知道少了什么数字，也太无能了，无法弄清楚，所以他们雇佣你来为他们做这件事。

万一动物园又丢了一个数字，他们希望你的程序能正常工作，不管总共有多少个数字。任务:

编写一个函数，将唯一数字的混洗数组从1到n，其中缺少一个元素（可以是包括n在内的任何数字）。返回这个缺失的数字。示例：

findNumber([1，3，4])应为2 findNumber([1，2，3])应为4 findNumber([4，2，3])应为1

我有困难，因为这是第一次测试时间复杂度的练习。有一个测试可以检查你的算法对于大型数组的执行时间是否少于一秒。以下是我写的测试:

import static org.junit.Assert.assertEquals;

import java.util.concurrent.TimeUnit;

import org.junit.Rule;
import org.junit.Test;
import org.junit.rules.Timeout;

public class NumberZooPatrolSampleTest {

    @Rule
    public Timeout globalTimeout = new Timeout(1, TimeUnit.SECONDS);

    @Test
    public void testDescriptionExamples() {
        assertEquals(2, findMissingNumber(1, 3));
        assertEquals(1, findMissingNumber(2, 3, 4));
        assertEquals(12, findMissingNumber(13, 11, 10, 3, 2, 1, 4, 5, 6, 9, 7, 8));
    }

    @Test
    public void testPerformanceIsLinear() {
        // Solutions with linear runtime should finish in about 200 to 300 ms.
        // 1. Generate an array with 999,999 numbers with increasing and
        //    decreasing values interleaved so sorting algorithms which
        //    are able detect pre-sorted arrays would still need
        //    at least loglinear time.
        // 2. Find the missing number 100 times.
        int[] numbers = generateNumbers(1_000_000, 66_667);
        for (int i = 0; i < 249_999; i++) {
            int temp = numbers[i * 2];
            numbers[i * 2] = numbers[999_997 - i * 2];
            numbers[999_997 - i * 2] = temp;
        }
        for (int i = 0; i < 100; i++)
            findMissingNumber(numbers.clone());
    }

    private static int findMissingNumber(int ... numbers) {
        return NumberZooPatrol.findMissingNumber(numbers);
    }

    private static int[] generateNumbers(int bound, int missingNumber) {
        if (missingNumber < 1 || missingNumber > bound)
            throw new IllegalArgumentException("Missing number is not in allowed range");
        int[] numbers = new int[bound - 1];
        int pos = 0;
        for (int i = 1; i <= bound; i++)
            if (i != missingNumber)
                numbers[pos++] = i;
        return numbers;
    }

}

我的第一个方法是逐个比较数组中的数字与该位置应该有的数字：

import java.util.*;
import java.util.stream.*;
public class NumberZooPatrol {
  public static int findMissingNumber(int[] numbers) {
    int[] clone = numbers.clone();
    Arrays.sort(clone);
    int i = 0;
    for(; i < clone.length; i++){
      if(clone[i] != i+1){
        break;
      }
    }
    return i+1;
  }
}

然而，它没有通过时间复杂度测试。

此外，我使用了另一种方法，其中我们得到了范围之和与当前数组总和之间的差值：

import java.util.*;
import java.util.stream.*;
public class NumberZooPatrol {
  public static int findMissingNumber(int[] numbers) {
    if(numbers.length == 0) return 1;
    int[] clone = numbers.clone();
    Arrays.sort(clone);
    int range = IntStream.rangeClosed(1,clone[clone.length-1]).sum();
    int sum = IntStream.of(clone).sum();
    return range - sum == 0 ? clone.length + 1 : range - sum;
  }
}

当我们执行时间复杂度测试时，它也会超时。

此外，我还阅读了：

• 如何在Java中生成序列整数的列表或数组
• 如何用java流对整数列表求和
• 制作数组的副本

如何用有效的算法从数组中得到缺失的数字？‽?

Answer 1

您可以使用两种方法在O（n）时间复杂度下完成它：

>

您可以使用n（n 1）/2公式找到数字的总和，并减去实际总和以获得丢失的数字。

您还可以 XOR 1 到 n 范围内的所有数字以及输入中的数字。结果将是缺少的数字。这是有效的，因为，具有自身的数字的XOR为零，而0 XOR任何数字都是数字本身。

例如：如果输入是[1,3,4]，缺少的数字是2。

(1 XOR 2 XOR 3 XOR 4) XOR (1 XOR 3 XOR 4) = 
(1 XOR 1) XOR (3 XOR 3) XOR (4 XOR 4) XOR 2 =
0 XOR 0 XOR 0 XOR 2 = 
0 XOR 2 =
2