平武建站

java怎么在给定的数组里面寻找重复数

本篇内容介绍了“java怎么在给定的数组里面寻找重复数”的有关知识，在实际案例的操作过程中，不少人都会遇到这样的困境，接下来就让小编带领大家学习一下如何处理这些情况吧！希望大家仔细阅读，能够学有所成！

创新互联从2013年开始，先为交口等服务建站，交口等地企业，进行企业商务咨询服务。为交口企业网站制作PC+手机+微官网三网同步一站式服务解决您的所有建站问题。

原题

给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。

示例 1:

输入: [1,3,4,2,2]
输出: 2

示例 2:

输入: [3,1,3,4,2]
输出: 3

说明：

  • 不能更改原数组（假设数组是只读的）。

  • 只能使用额外的 O(1) 的空间。

  • 时间复杂度小于 O(n2) 。

  • 数组中只有一个重复的数字，但它可能不止重复出现一次。

解题

普通思路

针对说明里的前两条，其实就分别对应了解题的两种思路：

  1. 先原地排序，再遍历寻找。

  2. 使用集合记录已经出现过的数字。

当然了，既然已经在说明里被禁止了， 那么就应该想想别的思路了。

我还想到了利用 bitMap 的思路，相当于用一个数字的二进制，各个位上是否为1来表示该数字是否出现过。但考虑到 java 里 int 的最大值是 (2^31 - 1)，long 的最大值也不过是(2^63 - 1)，那都是要求 n 不能大于100的。因此，这种思路也是暂时不可取的。

抽象为环形链表II

如果将数组的下标和值抽象成链表的话，出现重复数字也就意味着出现链表中有环，那么这道题就是之前做到的力扣142——环形链表II一模一样了。

我们举例说明一下，假设数组是[1, 5, 7, 3, 2, 4, 6, 7]，那么将其转化成的链表就是：0 -> 1 -> 5 -> 7 -> 3 -> 2 -> 4 -> 6 -> 7 ....无限循环。

那我们就可以借助快慢指针：

  1. 快指针一次走两步，慢指针一次走一步，直到他们相遇；

  2. 快指针再次从起点出发，但此时两个指针都是一次走一步；

  3. 当他们再次相遇后，相遇点就是重复的整数。

接下来让我们看看代码：

class Solution {
   public int findDuplicate(int[] nums) {
       // 参考环形链表II，利用快慢指针
       // 快指针一次走两步，慢指针一次走一步，当他们相遇后
       // 快指针再次从起点出发，但此时两个指针都是一次走一步
       // 当他们再次相遇后，相遇点就是重复的整数

       int slow = nums[0];
       int fast = nums[nums[0]];
       while (slow != fast) {
           slow = nums[slow];
           fast = nums[nums[fast]];
       }

       fast = 0;
       while (slow != fast) {
           slow = nums[slow];
           fast = nums[fast];
       }

       return fast;
   }
}

提交OK，时间复杂度为：O(n)，空间复杂度是：O(1)。

“java怎么在给定的数组里面寻找重复数”的内容就介绍到这里了，感谢大家的阅读。如果想了解更多行业相关的知识可以关注创新互联网站，小编将为大家输出更多高质量的实用文章！


当前题目：java怎么在给定的数组里面寻找重复数
本文路径：http://pwwzsj.com/article/pijdjc.html

其他资讯