文章目录
  1. 1. Find the Duplicate Number
  2. 2.

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.

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.

找出重复数字的话,上来可能想到用Map,但是题中限定要常数的额外空间,所以用Map记录是不可行的.
并且不能改动原数组,所以排序也是不可行的.

一开始是想用分治的方法,将数组分为两部分(A,B),如果A中有重复的数,那么答案就在A中,如果在B中同理.
如果A,B中都没有的话,那么说明有一个数在A,另一个在B.
然而发现这种一个在A一个在B的情况无法处理,只能遍历,那么时间复杂度在最坏的情况下就是O(n^2)了.

后来注意到题中有个条件,一共(n+1)个整数,这些整数的范围都在(1-n)之间.
那么就可以用二分法,取(1-n)的中位数n/2,遍历一次数组统计大于n/2和小于n/2的数的个数,如果大于n/2的数多于一半,说明重复的数是大于n/2的,反之同理.
这样一次就可以排除一半的数,时间复杂度为O(nlogn).

代码如下:

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
28
29
30
31
32
33
34
35
36
37
38
def __find_duplicate(nums,start_num,middle_num,end_num)
less = 0
eqls = 0
greater = 0
nums.each{|x|
next if x < start_num || x > end_num
if x > middle_num
greater += 1
elsif x < middle_num
less += 1
else
eqls += 1
end
}
return middle_num if eqls > 1
return -1 if less < 2 && greater < 2
m1 = start_num + (middle_num - start_num) / 2
m2 = middle_num + (end_num - middle_num) / 2
if less > middle_num - start_num
return __find_duplicate(nums,start_num,m1,middle_num)
elsif greater > end_num - middle_num
return __find_duplicate(nums,middle_num,m2,end_num)
else
a = __find_duplicate(nums,start_num,m1,middle_num)
return a if a != -1
b = __find_duplicate(nums,middle_num,m2,end_num)
return b if b != -1
return -1
end
end
# @param {Integer[]} nums
# @return {Integer}
def find_duplicate(nums)
n = nums.length
m = 1 + (n - 1) / 2
__find_duplicate(nums,1,m,n)
end
文章目录
  1. 1. Find the Duplicate Number
  2. 2.