Find Missing Number From a Given Array in Java – 用 Java 从给定数组中查找缺失的数字

最后修改: 2024年 1月 7日

中文/混合/英文(键盘快捷键：t)

1. Overview

1.概述

Finding the missing number from a specified range within an array in Java can be useful in various scenarios, such as data validation, ensuring completeness, or identifying gaps in a dataset.

在 Java 数组中查找指定范围内缺少的数字在各种情况下都非常有用，例如数据验证、确保完整性或识别数据集中的空白。

In this tutorial, we’ll learn multiple approaches to finding a single missing number from an array in the integer range [1-N].

在本教程中，我们将学习从整数范围[1-N]内的数组中查找单个缺失数的多种方法。

2. Understanding the Scenario

2.了解情景

Let’s imagine that we’ve got the numbers array with integers in the range [1-9], both inclusive:

假设我们有一个 numbers 数组，数组中的整数范围为 [1-9]，包含这两个整数：

int[] numbers = new int[] { 1, 4, 5, 2, 7, 8, 6, 9 };

Now, we aim to find the missing number from the array in the range [1-9].

现在，我们的目标是在 [1-9] 范围内找到数组中缺少的数字。

To generalize the problem statement, we can compute the length of the array and set the upper bound, N:

为了推广问题陈述，我们可以计算数组的长度，并设置上界 N ：

int N = numbers.length + 1;

In the following sections, we’ll learn different ways to find the missing number from a given array in the range [1-N].

在下面的章节中，我们将学习在 [1-N] 范围内从给定数组中找出缺失数的不同方法。

3. Using Arithmetic Sum

3.使用算术和

Let’s start by using arithmetic sum to find the missing number from the numbers array.

让我们从使用算术求和开始，找出 numbers 数组中缺少的数字。

First, we’ll compute the expected sum of the arithmetic progression in the range [1-N] and the actual sum of the array:

首先，我们将计算 算术级数在 [1-N] 范围内的预期和以及数组的实际和：

int expectedSum = (N * (N + 1)) / 2;
int actualSum = Arrays.stream(numbers).sum();

Next, we can subtract the actualSum from the expectedSum to get the missingNumber:

接下来，我们可以用 expectedSum 减去 actualSum 得出 missingNumber ：

int missingNumber = expectedSum - actualSum;

Lastly, let’s verify the result:

最后，让我们来验证一下结果：

assertEquals(3, missingNumber);

It’s correct!

这是正确的！

4. Using XOR Properties

4.使用 XOR 属性

Alternatively, we can use two interesting properties of the xor operator (^) to solve our use case:

或者，我们可以使用 xor 运算符 (^) 的两个有趣属性来解决我们的用例：

  • X^X = 0: When we xor a number with itself, we get zero.
  • X^0 = X: When we xor a number with zero, we get the same number back.

First, we’ll do the xor operation on all the integer values in the closed range [1-9] using the reduce function:

首先，我们将使用 reduce 函数对封闭范围 [1-9] 中的所有整数值进行 xor 运算：

int xorValue = IntStream.rangeClosed(1, N).reduce(0, (a, b) -> a ^ b);

We used 0 and (a, b) -> a ^ b, which is a lambda expression, as the identity and accumulator, respectively, for the reduce() operation.

我们使用 0 和 (a, b) -> a ^ b,（lambda 表达式）分别作为 reduce() 操作的 identity 和累加器。

Next, we’ll continue the xor operation with the integer values from the numbers array:

接下来，我们将继续对数字数组中的整数值进行 xor 操作：

xorValue = Arrays.stream(numbers).reduce(xorValue, (x, y) -> x ^ y);

Since every number except the missing number comes twice, the xorValue will only contain the missing number in the numbers array from the range [1-9].

由于除了缺失的数字外，每个数字都有两次，因此 xorValue 将只包含 numbers 数组中范围为 [1-9] 的缺失数字。

Lastly, we should verify that our approach gives the correct results:

最后，我们应该验证我们的方法是否得出了正确的结果：

assertEquals(3, xorValue);

Great! We got this one right.

太好了我们做对了

5. Using Sorting

5.使用排序

Our input array, numbers, is expected to contain all the consecutive values in the range [1-N], except for the missing number. So, if we sort the array, it’ll be convenient to spot the missing number where we don’t see a consecutive number.

我们的输入数组 numbers, 预计将包含范围 [1-N] 内的所有连续值，但缺失的数字除外。因此，如果我们对数组进行排序，就可以很方便地在没有连续数字的地方发现缺失的数字。

First, let’s sort the numbers array:

首先，让我们对 numbers 数组进行排序：

Arrays.sort(numbers);

Next, we can iterate over the numbers array and check if the value at index is index+1 or not:

接下来，我们可以遍历 numbers 数组，检查 index 中的值是否为 index+1 ：

int missingNumber = -1;
for (int index = 0; index < numbers.length; index++) {
    if (numbers[index] != index + 1) {
        missingNumber = index + 1;
        break;
    }
}

When the condition fails, it implies that the expected value, index + 1, is missing from the array. So, we set the missingNumber and did an early exit from the loop.

当条件失败时，这意味着数组中缺少预期值 index + 1。因此，我们设置了 missingNumber 并提前退出了循环。

Finally, let’s check that we’ve got the desired output:

最后，让我们检查一下是否获得了所需的输出结果：

assertEquals(3, missingNumber);

The result looks correct. However, we must note that we mutated the original input array in this case.

结果看起来是正确的。但是，我们必须注意，在这种情况下，我们改变了原始输入数组。

6. Tracking With a boolean Array

6.使用 布尔数组进行跟踪

In the sorting approach, there were two major drawbacks:

分类方法有两大缺陷：

  • Overhead costs for sorting
  • Mutation of the original input array

We can mitigate these issues by using a boolean array to keep track of the present numbers.

我们可以使用 布尔数组来跟踪当前数字，从而缓解这些问题。

First, let’s define present as a boolean array of size N:

首先，让我们将 present 定义为大小为 N 的 布尔数组：

boolean[] present = new boolean[N];

We must recall that N was initialized as numbers.length + 1.

我们必须记得，N 初始化为 numbers.length + 1。

Next, we’ll iterate over the numbers array and mark the presence of each number in the present array:

接下来，我们将遍历数字数组，并在present数组中标记每个数字的存在：

int missingNumber = -1;
Arrays.stream(numbers).forEach(number -> present[number - 1] = true);

Further, we’ll perform another iteration, but on the present array, to find the number that’s not marked as present:

此外，我们将对 present 数组执行另一次迭代，以找出未标记为存在的数字：

for (int index = 0; index < present.length; index++) {
    if (!present[index]) {
        missingNumber = index + 1;
        break;
    }
}

Lastly, let’s verify our approach by checking the value of the missingNumber variable:

最后，让我们通过检查 missingNumber 变量的值来验证我们的方法：

assertEquals(3, missingNumber);

Perfect! Our approach worked. Further, we must note that we used additional space of N bytes as each boolean value will take 1 byte in Java.

太完美了我们的方法成功了。此外，我们必须注意到，我们使用了 N 字节的额外空间，因为在 Java 中，每个 boolean 值占用 1 个字节。

7. Tracking With Bitset

7.使用 Bitset 跟踪

We can optimize the space complexity by using Bitset over a boolean array.

我们可以通过在 boolean 数组上使用 Bitset 来优化空间复杂度。

BitSet bitSet = new BitSet(N);

With this initialization, we’ll use only enough space to represent N bits. It’s a considerable optimization when the value of N is quite high.

通过这种初始化，我们将只使用足够的空间来表示 N 位。当 N 的值相当大时，这是一个相当大的优化。

Next, let’s iterate over the numbers array and mark their presence by setting a bit at their position in bitset:

接下来，让我们遍历 numbers 数组，并通过在 bitset 中的位置设置一个 bit 来标记它们的存在：</em

for (int num : numbers) {
    bitSet.set(num);
}

Now, we can find the missing number by checking the bit that’s not set:

现在，我们可以通过检查未设置的位来找到缺失的数字：

int missingNumber = bitSet.nextClearBit(1);

Finally, let’s confirm that we’ve got the correct value in the missingNumber:

最后，让我们确认 missingNumber 中的值是否正确：

assertEquals(3, missingNumber);

Fantastic! It looks like we nailed this one.

太棒了看来我们成功了。

8. Conclusion

8.结论

In this tutorial, we learned how to find a missing number from an array. Further, we explored multiple ways to solve the use case, such as arithmetic sum, xor operations, sorting, and additional data structures, like Bitset and boolean array.

在本教程中，我们学习了如何从数组中查找缺少的数字。此外，我们还探索了解决该用例的多种方法，例如算术求和、Xor 运算、排序和其他数据结构，如 Bitset 和 boolean 数组。

As always, the code from this article is available over on GitHub.

与往常一样，本文中的代码可在 GitHub 上获取。