本教程详细介绍了在java中如何查找给定范围内（从1到指定最大值）未出现在无序整数数组中的数字。文章分析了常见的错误，并提供了两种主要的解决方案：一种是利用`hashset`进行高效查找，适用于大型数组；另一种是实现自定义的线性查找方法，适用于小型数组，并简要提及了排序加二分查找的策略，旨在帮助开发者选择最适合其场景的方法。
识别数组中缺失的数字
在编程实践中，我们经常会遇到需要在一个指定范围内，找出哪些数字没有出现在一个给定的无序数组中的场景。例如，给定一个最大值max和一个整数数组A，我们的目标是打印出所有从1到max之间，但不在数组A中的数字。
常见误区分析
初学者在尝试解决此类问题时，可能会倾向于创建一个有序的参考数组，然后将输入数组中的元素与参考数组进行比较。然而，如果比较逻辑不当，可能会导致打印出数组中“已包含”的数字，而非“未包含”的数字。
以下是一个典型的错误示例，它错误地打印了数组A中已存在的数字：
public class Test { public static void main(String[] args) { int max = 5; int[] A = {1, 2, 3, 5}; // 创建一个有序的参考数组B int[] B = new int[max]; int num = 1; for (int i = 0; i < max; i++) { B[i] = num; num++; } // 错误的检查逻辑：这将打印A中已包含的数字 for (int i = 0; i < A.length; i++) { for (int j = 0; j < B.length; j++) { if (A[i] == B[j]) { System.out.println(B[j]); // 打印的是A中存在的数字 } } } }}
上述代码的本意是找出缺失的数字，但由于if (A[i] == B[j])条件成立时打印B[j]，它实际上输出了数组A中已有的元素（1, 2, 3, 5），这与我们的目标相反。要找到缺失的数字，我们需要的是在外部循环中遍历完整的范围，并在内部判断当前数字是否不在数组A中。
立即学习“Java免费学习笔记（深入）”；
解决方案
为了正确地找出并打印缺失的数字，我们可以采用以下几种策略。
方案一：使用 HashSet 进行高效查找
当处理大型数组时，将输入数组转换为 HashSet 是一个非常高效的方法。HashSet 提供了平均 O(1) 时间复杂度的 contains() 方法，这使得查找操作极其迅速。
实现步骤：
Shakker
多功能AI图像生成和编辑平台
103 查看详情 将输入的整数数组转换为 HashSet。这将允许我们快速检查某个数字是否存在于原始数组中。从1遍历到 max。对于范围内的每个数字，使用 HashSet 的 contains() 方法检查它是否在集合中。如果 contains() 返回 false，则表示该数字是缺失的，将其打印出来。
示例代码：
import java.util.Collections;import java.util.HashSet;import java.util.Set;public class MissingNumberFinder { public static void main(String[] args) { int max = 5; // 注意：对于Set，需要使用包装类Integer Integer[] A = {1, 2, 3, 5}; // 将数组A的元素添加到HashSet中 Set presentNumbers = new HashSet(); Collections.addAll(presentNumbers, A); System.out.println("缺失的数字 (使用 HashSet):"); // 遍历从1到max的每个数字 for (int i = 1; i <= max; i++) { // 如果当前数字不在presentNumbers集合中，则它是缺失的 if (!presentNumbers.contains(i)) { System.out.println(i); } } }}
优点：
效率高： 对于大型数组，构建 HashSet 的时间复杂度是 O(N) (N为数组长度)，而后续的 contains() 操作平均时间复杂度是 O(1)。因此，整个查找过程的平均时间复杂度是 O(N + max)。代码简洁： 利用Java集合框架的强大功能，代码可读性好。
注意事项：
HashSet 存储的是对象，所以当从原始类型数组（如int[]）转换为集合时，需要使用包装类（如Integer[]）。
方案二：自定义线性查找方法
如果数组规模较小，或者希望避免创建额外的 Set 对象开销，可以实现一个自定义的线性查找函数。这种方法在每次检查时都需要遍历整个原始数组。
实现步骤：
创建一个辅助函数 contains(Integer[] arr, int x)，它遍历数组 arr，如果找到 x 则返回 true，否则返回 false。从1遍历到 max。对于范围内的每个数字，调用自定义的 contains() 方法检查它是否在原始数组中。如果 contains() 返回 false，则打印该数字。
示例代码：
public class MissingNumberFinderCustom { // 自定义查找函数，检查数组arr中是否包含数字x public static boolean contains(Integer[] arr, int x) { for (int j = 0; j < arr.length; j++) { if (arr[j] == x) { return true; } } return false; } public static void main(String[] args) { int max = 5; Integer[] A = {1, 2, 3, 5}; System.out.println("缺失的数字 (使用自定义查找):"); // 遍历从1到max的每个数字 for (int i = 1; i <= max; i++) { // 如果当前数字不在数组A中，则它是缺失的 if (!contains(A, i)) { System.out.println(i); } } }}
优点：
内存开销小： 不需要创建额外的 HashSet 对象。简单直观： 对于理解查找逻辑而言，直接遍历数组更易于理解。
缺点：
效率较低： contains() 方法的每次调用都需要 O(N) 的时间复杂度（N为数组长度）。因此，整个查找过程的时间复杂度是 O(max * N)。对于大型数组和较大的 max 值，性能会显著下降。
方案三：排序与二分查找（进阶）
另一种优化方法是先对原始数组进行排序，然后利用二分查找。如果输入数组本身已经是有序的，或者排序的开销可以接受，这种方法会非常高效。
实现步骤：
对数组 A 进行排序。从1遍历到 max。对于范围内的每个数字，使用 Arrays.binarySearch() 方法在已排序的数组 A 中进行查找。如果 binarySearch() 返回的值小于0，则表示该数字不存在于数组中，将其打印出来。
示例代码（概念性，不提供完整代码）：
import java.util.Arrays;// ...// 对数组A进行排序// Arrays.sort(A); // for (int i = 1; i <= max; i++) {// if (Arrays.binarySearch(A, i) < 0) { // 如果查找结果小于0，表示未找到// System.out.println(i);// }// }// ...
优点：
效率高： 排序的时间复杂度通常为 O(N log N)，二分查找的时间复杂度为 O(log N)。因此，总时间复杂度为 O(N log N + max log N)。对于大型数组，这比线性查找高效。适用于已排序数组： 如果输入数组经常是或可以假定为已排序，此方法非常理想。
缺点：
修改原始数组： Arrays.sort() 会修改原始数组的顺序。排序开销： 如果数组非常大且无序，排序本身会带来一定的开销。
总结与选择建议
根据上述分析，我们可以得出以下结论和选择建议：
对于大多数场景和大型数组，推荐使用 HashSet 方案。 它在平均情况下提供了最佳的性能（O(N + max)），并且代码简洁易懂。对于小型数组，或者对内存使用有严格限制，且性能要求不极致的场景，可以考虑自定义线性查找方法。 它的实现最简单，但时间复杂度较高（O(max * N)）。如果数组经常是有序的，或者排序的开销可以接受，并且希望获得较高的性能，可以考虑排序加二分查找方案。
使用上述任何一种正确的方法，对于输入 max = 5 和 A = {1, 2, 3, 5}，预期的输出都将是：
4
在实际开发中，根据具体的数据规模、性能要求以及对内存的限制，选择最合适的方案至关重要。
以上就是如何在Java数组中查找并打印缺失的数字的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1104112.html
微信扫一扫 
支付宝扫一扫 
