java - 使用有效的算法从数组中获取缺失的数字？‽？

Question

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

Background:

You're working in a number zoo, and it seems that one of the numbers has gone missing!

Zoo workers have no idea what number is missing, and are too incompetent to figure it out, so they're hiring you to do it for them.

In case the zoo loses another number, they want your program to work regardless of how many numbers there are in total. Task:

Write a function that takes a shuffled array of unique numbers from 1 to n with one element missing (which can be any number including n). Return this missing number. Examples:

findNumber([1, 3, 4]) should be 2 findNumber([1, 2, 3]) should be 4 findNumber([4, 2, 3]) should be 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;
  }
}

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

此外我还读过:

• How can I generate a list or array of sequential integers in Java?
• How to sum a list of integers with java streams?
• Make copy of an array

我们如何通过高效的算法从数组中获取缺失的数字？‽？

Answer 1

您可以使用两种方法以 O(n) 时间复杂度完成此操作:

1. 您可以使用 n(n+1)/2 公式求出数字的总和，然后减去实际的总和即可得到缺失的数字。

2. 您还可以对 1 到 n 范围内的所有数字以及输入中的数字进行异或。结果将是缺失的数字。这是有效的，因为数字与其自身的异或为零，而 0 任何数字的异或都是数字本身。

例如: 如果输入是 [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