Question
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(n2). - There is only one duplicate number in the array, but it could be repeated more than once.
Solution 1 -- Binary Search
题目要求时间复杂度小于O(n2)，于是我们就想有没有O(n log n)或者O(n)的做法。一些排序算法是O(n log n)，但是题目要求不能更改原序列且空间复杂度为O(1)。
Binary search的复杂度是O(log n)，前提是排好序的数组。所以肯定不能用输入数组来进行二分查找。
这一题提供了一个思路是对可行解序列／集合进行二分查找。
由于题目中有明确的各个元素的取值范围，我们可以判断出解一定在[1, n]这个区间内。start = 1, end = n。对于每个mid值，我们计算等于mid的count和小于等于mid的count。
注意：
smallerCount 是和mid值比较。比如mid = 5，那么如果smallerCount <= 5，说明解一定不在[1,5]这个区间内。
public class Solution {
public int findDuplicate(int[] nums) {
int start = 1, end = nums.length - 1, mid;
while (start + 1 < end) {
mid = (end - start) / 2 + start;
int smallerMid = 0;
for (int i : nums) {
if (i <= mid) {
smallerMid++;
}
}
// Compare with mid
if (smallerMid <= mid) {
start = mid;
} else{
end = mid;
}
}
int countStart = 0;
for (int i : nums) {
if (i == start) {
countStart++;
}
}
if (countStart > 1) {
return start;
}
return end;
}
}
Solution 2
参考Discuss，发现有O(n)的解法
参考Linked List II，我们将输入的array也可看作是list，每个数组元素代表这个node的next
public class Solution {
public int findDuplicate(int[] nums) {
if (nums == null || nums.length < 2) {
return 0;
}
int slow = nums[0];
int fast = nums[slow];
while (fast != slow) {
slow = nums[slow];
fast = nums[nums[fast]];
}
fast = 0;
while (fast != slow) {
slow = nums[slow];
fast = nums[fast];
}
return slow;
}
}