Java 程序查找未排序数组中缺失的最小正数

在软件开发领域，高效地解决基于数组的问题至关重要，尤其是在技术面试和竞争性编程中。其中一个问题是如何找出未排序数组中缺失的最小正数。这个问题可以测试程序员操纵和遍历数组的能力，以及他们对时间和空间复杂度的理解。

方法

方法 1：使用排序

方法

• 对数组进行排序。
• 遍历已排序的数组，查找第一个缺失的正数。

实施

• 对数组进行排序。
• 从 1 开始遍历数组，并检查每个正整数是否存在。

文件名：MissingPositiveNumber.java

输出

 
2   

时间复杂度： O(nlogn)，由于排序。

空间复杂度： 如果使用原地排序，则为 O(1)

方法 2：使用哈希

方法

• 使用 HashSet 存储数组中的所有正数。
• 从 1 开始向上遍历，并检查每个数字是否在 HashSet 中。

实施

• 遍历数组并将所有正数添加到 HashSet 中。
• 从 1 开始检查它是否在 HashSet 中。一直进行直到找到缺失的数字。

文件名：MissingPositiveNumber.java

输出

 
2   

时间复杂度： 插入和搜索操作均为 O(n)。

空间复杂度： O(n)，用于在 HashSet 中存储元素。

方法 3：使用索引映射（最优解）

方法

• 使用数组本身通过将每个数字放置在其对应的索引处来跟踪正数是否存在（数字 1 放在索引 0，数字 2 放在索引 1，依此类推）。
• 再次遍历数组，查找不匹配其对应数字的第一个索引。

实施

• 遍历数组并将每个数字放置在其对应的索引处。
• 遍历数组，查找第一个值不等于索引 + 1 的索引。

文件名：MissingPositiveNumber.java

输出

 
2   

时间复杂度：O(n)

空间复杂度： O(1)，因为重排是原地完成的。

结论

识别未排序数组中缺失的最小正数是一个经典问题，可以使用各种技术来解决。通过本文，我们研究了三种不同的方法：排序、哈希和索引映射。每种方法都有其优点和权衡。

排序方法虽然简单，但对于大型数据集来说不是最优的。哈希方法在改进时间复杂度的同时，也增加了额外的空间成本。而索引映射技术则通过线性的时间和常数的空间使用，实现了两者的最佳结合。

通过理解和实现这些方法，开发人员可以提高他们的解决问题的能力，并为复杂的技能挑战做好准备。