0287. Find the Duplicate Number

287. Find the Duplicate Number #

题目 #

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

Example 1:


Input: [1,3,4,2,2]
Output: 2

Example 2:


Input: [3,1,3,4,2]
Output: 3

Note:

  • You must not modify the array (assume the array is read only).
  • You must use only constant, O(1) extra space.
  • Your runtime complexity should be less than O(n^2).
  • There is only one duplicate number in the array, but it could be repeated more than once.

题目大意 #

给出 n + 1 个数,这些数是在 1-n 中取值的,同一个数字可以出现多次。要求找出这些数中重复的数字。时间复杂度最好低于 O(n^2),空间复杂度为 O(1)。

解题思路 #

  • 这道题比较巧的思路是,将这些数字想象成链表中的结点,数组中数字代表下一个结点的数组下标。找重复的数字就是找链表中成环的那个点。由于题目保证了一定会有重复的数字,所以一定会成环。所以用快慢指针的方法,快指针一次走 2 步,慢指针一次走 1 步,相交以后,快指针从头开始,每次走一步,再次遇见的时候就是成环的交点处,也即是重复数字所在的地方。
  • 这一题有多种做法。可以用快慢指针求解。还可以用二分搜索:(这里的题解感谢 @imageslr 指出错误):
    1. 假设有 n+1 个数,则可能重复的数位于区间 [1, n] 中。记该区间最小值、最大值和中间值为 low、high、mid
    2. 遍历整个数组,统计小于等于 mid 的整数的个数,至多为 mid 个
    3. 如果超过 mid 个就说明重复的数存在于区间 [low,mid] (闭区间)中;否则,重复的数存在于区间 (mid, high] (左开右闭)中
    4. 缩小区间,继续重复步骤 2、3,直到区间变成 1 个整数,即 low == high
    5. 整数 low 就是要找的重复的数
  • 另外一个做法是,先将数组排序,依照下标是从 0 开始递增的特性,那么数组里面的数字与下标的差值应该是越来越大。如果出现了相同的数字,下标变大,差值应该比前一个数字小,出现了这个情况就说明找到了相同数字了。

代码 #


package leetcode

import "sort"

// 解法一 快慢指针
func findDuplicate(nums []int) int {
	slow := nums[0]
	fast := nums[nums[0]]
	for fast != slow {
		slow = nums[slow]
		fast = nums[nums[fast]]
	}
	walker := 0
	for walker != slow {
		walker = nums[walker]
		slow = nums[slow]
	}
	return walker
}

// 解法二 二分搜索
func findDuplicate1(nums []int) int {
	low, high := 0, len(nums)-1
	for low < high {
		mid, count := low+(high-low)>>1, 0
		for _, num := range nums {
			if num <= mid {
				count++
			}
		}
		if count > mid {
			high = mid
		} else {
			low = mid + 1
		}
	}
	return low
}

// 解法三
func findDuplicate2(nums []int) int {
	if len(nums) == 0 {
		return 0
	}
	sort.Ints(nums)
	diff := -1
	for i := 0; i < len(nums); i++ {
		if nums[i]-i-1 >= diff {
			diff = nums[i] - i - 1
		} else {
			return nums[i]
		}
	}
	return 0
}


⬅️上一页

下一页➡️

Calendar Sep 6, 2020
Edit Edit this page
本站总访问量:  次 您是本站第  位访问者