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

问题描述

我正在做以下编程练习：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;
  }
}

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

另外我读过：

我们如何使用有效的算法从数组中获取缺失的数字？‽？

标签： javaarraysalgorithmperformanceint

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

问题描述

解决方案

推荐阅读