echo

任生命穿梭 时间的角落

0%

寻找重复数

Posted on Edited on In Valine:

287. 寻找重复数

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

示例 1:

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

示例 2:

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

说明：

  1. 不能更改原数组（假设数组是只读的）。
  2. 只能使用额外的 O(1) 的空间。
  3. 时间复杂度小于 O(n2) 。
  4. 数组中只有一个重复的数字，但它可能不止重复出现一次。

方法一： 二分查找

定义 cnt[i] 表示 nums 数组中小于等于 i 的数有多少个，假设重复的数是 target，那么[1, target-1]里的所有数满足cnt[i] < i，[target, n]里的所有数满足 cnt[i] > i。

以示例 1 为例，列出 cnt 的值

nums 1 2 3 4
cnt 1 3 4 5

示例中重复的整数是2，[1, 1]中的数满足 cnt[i] <= i， [2,4]中的数满足cnt[i] >= i。

由于只有一个整数重复了两次以上，我们考虑 target 整数出现了 2 次和 3 次及以上的情况：

  • target 出现了两次 [1, target -1]范围内满足 cnt[i] = i
  • target 出现了三次及以上，代表[1,n]范围内有整数没有出现，当没有出现的整数 i 小于 target 则[i, target]的cnt 值减一，满足条件。当没有出现的整数 j 大于 target 则[target, j-1]的cnt 值均加一，满足条件。

那么我们怎么利用 cnt 数组来找到重复出现的数字呢？

由于 nums 数组是有序的，我们可以想到使用二分查找，在二分查找的过程中统计 cnt 的值，根据 cnt 的值来判断重复的数字在[left, mid - 1] 或[mid + 1, right]区间中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public int findDuplicate(int[] nums) {
        int n = nums.length;
        int l = 0, r = n - 1, ans = -1;
        while(l <= r){
            //统计cnt
            int mid = l + (r - l) / 2;
            int cnt = 0;
            for(int i = 0; i < n ; ++i){
                if(nums[i] <= mid){
                    cnt++;
                }
            }
			//cnt[i] <= mid，重复的数字在[mid + 1, r]区间
            if(cnt <= mid){
                l = mid + 1;
            }else{
                //cnt[i] > mid，重复的数字在[l, mid - 1]
                r = mid - 1;
                //当 l > r时，mid 为重复的数字 
                ans = mid;
            }
        }

        return ans;
    }
}

时间复杂度O(nlogn) 空间复杂度O(1)

方法二：快慢指针

快慢指针通常用来判断链表中是否有环，我们可以对 nums 数组建图每个位置 i 连一条 i -> nums[i]的边，由于存在重复的数字target，target 位置至少有两条指向它的边，因此存在环，就转换为找环的入口问题。

以示例 1 为例我们建立得到的图如下

image-20200526115632169

我们可以先使用快慢指针走进环中，再将慢指针放到起点，快慢指针一起走，直到快慢指针相遇就是结果。

为什么将慢指针放到起点一起走，直到快慢指针相遇就是结果呢？。

假设环长为 L，从起点到环的入口的步数是 a，从环的入口继续走 b 步到达相遇位置，从相遇位置继续走 c 步回到环的入口。快指针比慢指针多走了 k 圈。表示为 2(a+b)=a+b+k L。进而得到 a=(k−1)L+(L−b)=(k−1)L+c

如果慢指针从起点出发，快指针从相遇位置出发，每次两个指针都移动一步，则慢指针走了 a 步之后到达环的入口，快指针在环里走了 k−1 圈之后又走了 c 步，由于从相遇位置继续走 c 步即可回到环的入口，因此快指针也到达环的入口。两个指针在环的入口相遇，相遇点就是答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int findDuplicate(int[] nums) {
        int slow = 0, fast = 0;
        //快慢指针相遇
        do{
            slow = nums[slow];
            fast = nums[nums[fast]];
        }while(slow != fast);
		//慢指针从头开始走，快慢指针相遇时得到环的入口点
        slow = 0;
        while(slow != fast){
            slow = nums[slow];
            fast = nums[fast];
        }
        return slow;
    }
}

时间复杂度O(n) 空间复杂度O(1)