题目描述
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(n2).
- There is only one duplicate number in the array, but it could be repeated more than once.
循环链表
- 假如有数组 1，3，4，2，5
- 那么对应下标 0，1，2，3，4
- 从下标为 0 出发，根据f(n) 计算出一个值，以这个值为新的下标，再用这个函数计算，以此类推，直到下标超界。这样可以产生一个类似链表一样的序列。 建立数组到下标的映射 0 -> 1 -> 3 -> 2 -> 4 -> 5 -> nullptr
- 如果有重复元素 ，那么此链表一定有环，并且重复元素即为环的入口，接下来就将转换成寻找链表环的入口的操作。
class Solution {
public:
int findDuplicate(vector<int>& nums) {
// vector<int> vec(nums);
// for(int i = 0; i < vec.size(); i++){
// while(i != nums[i] - 1){
// if(nums[i] == nums[nums[i] - 1]){
// return nums[i];
// }
// else{
// swap(nums[i], nums[nums[i] - 1]);
// }
// }
// }
// return -1;
int slow = 0;
int fast = 0;
slow = nums[slow];
fast = nums[nums[fast]];
while(slow != fast){
slow = nums[slow];
fast = nums[nums[fast]];
}
int pre = 0;
while(pre != slow){
pre = nums[pre];
slow = nums[slow];
}
return pre;
}
};
比较交换
- 如果当前的数字不等于当前的位置，就把当前数字换到其对应的位置上去，然后依次类推，直到找到重复的元素为止。
比较交换代码实现
class Solution { public: int findDuplicate(vector<int>& nums) { for(int i = 0; i < nums.size(); i++){ while(nums[i] - 1 != i){ if(nums[i] == nums[nums[i] - 1]){ return nums[i]; } swap(nums[i], nums[nums[i] - 1]); } } return -1; } };
STL解题思路
- unordered_set使用
- 如果能够在set集合里找到，则s.count(num)返回相应的个数
- unordered_set containers do not allow for duplicate values, this means that the function actually returns 1 if an element with that value exists in the container, and zero otherwise.
- unordered_set不允许有重复值，所以count实际返回值要么是1要么是0.
- set基于红黑树实现，红黑树具有自动排序的功能，因此map内部所有的数据，在任何时候，都是有序的。
unordered_set基于哈希表，数据插入和查找的时间复杂度很低，几乎是常数时间，而代价是消耗比较多的内存，无自动排序功能。底层实现上，使用一个下标范围比较大的数组来存储元素，形成很多的桶，利用hash函数对key进行映射到不同区域进行保存。
- set基于红黑树实现，红黑树具有自动排序的功能，因此map内部所有的数据，在任何时候，都是有序的。
C++代码
class Solution {
public:
int findDuplicate(vector<int>& nums) {
unordered_set<int> s;
for(auto num : nums){
if(!s.count(num)){
s.insert(num);
}
else{
return num;
}
}
return -1;
}
};
