本文共 3180 字,大约阅读时间需要 10 分钟。
Given an array of integers nums
containing n + 1
integers where each integer is in the range [1, n]
inclusive.
There is only one duplicate number in nums, return this duplicate number.
Follow-ups:
- How can we prove that at least one duplicate number must exist in nums?
- Can you solve the problem without modifying the array nums?
- Can you solve the problem using only constant, O ( 1 ) O(1) O(1) extra space?
- Can you solve the problem with runtime complexity less than O ( n 2 ) O(n^2) O(n2)?
Example 1:
Input: nums = [1,3,4,2,2]Output: 2
Example 2:
Input: nums = [3,1,3,4,2]Output: 3
Example 3:
Input: nums = [1,1]Output: 1
Example 4:
Input: nums = [1,1,2]Output: 1
Constraints:
2 <= n <= 3 * 104
nums.length == n + 1
1 <= nums[i] <= n
- All the integers in
nums
appear only once except for precisely one integer which appears two or more times.
题意:给定一个包含 n + 1
个整数的数组 nums
,其数字都在 1
到 n
之间(包括 1
和 n
),可知至少存在一个重复的整数。假设只有一个重复的整数,找出这个重复的数。
注意:不能更改原数组。只能使用额外的 O ( 1 ) O(1) O(1) 的空间,时间复杂度小于 O ( n 2 ) O(n^2) O(n2) 。数组中只有一个重复的数字,但它可能不止重复出现一次。
证明在数组
nums
中必然存在至少一个重复元素……很简单,不过是鸽巢定理的逆向罢了——如果要把n + 1
个物体放进n
个盒子,那么至少有一个盒子包含两个或更多个物体;如果把n
个物体放进n + 1
个盒子,允许重复装入某个物体,那么至少有两个盒子包含同样的物体。
解法1 辅助空间(哈希表)
使用哈希表记录每个整数的出现次数,如果发现某个元素出现次数 > 1
,就直接返回:
class Solution { public: int findDuplicate(vector & nums) { unordered_maprec; int n = nums.size(); for (int i = 0; i < n; ++i) { ++rec[nums[i]]; if (rec[nums[i]] > 1) return nums[i]; } return 0; }};
或者改成哈希集合:
class Solution { public: int findDuplicate(vector & nums) { unordered_set rec; int n = nums.size(); for (int i = 0; i < n; ++i) { if (rec.find(nums[i]) != rec.end()) return nums[i]; rec.insert(nums[i]); } return 0; }};
或者改成位图:
class Solution { public: int findDuplicate(vector & nums) { bitset<30010> bst; int n = nums.size(); for (int i = 0; i < n; ++i) { if (bst[nums[i]]) return nums[i]; bst[nums[i]] = 1; } return 0; }};
使用位图的效率更高一些:
执行用时:20 ms, 在所有 C++ 提交中击败了60.79% 的用户内存消耗:11.2 MB, 在所有 C++ 提交中击败了15.47% 的用户
解法2 快慢指针
这道题的 O ( 1 ) O(1) O(1) 空间、 O ( n ) O(n) O(n) 时间、不修改数组的解法,我还是看了评论区里的大佬讲解才做出来的。快慢指针,一个时间复杂度为 O ( n ) O(n) O(n) 的算法——对于链表问题,快慢指针可以判断环的存在与入环的位置。难点是如何将数组 nums[]
配合其下标抽象为链表问题。
一个例子是:nums = [1,3,4,2,2]
,构造为链表就是:0(索引0) -> 1(nums[0]) -> 3(nums[1]) -> 2(nums[3]) -> 4(nums[2]) -> 2(nums[4])
。显而易见,重复值 2
会导致环的出现,它也是入环的第一个结点。我们可以利用快慢指针找到环的起始位置:
- 快慢指针都初始化为
0
; - 快指针
hi
每次走两步,慢指针每次走1
步,直到两个指针相遇; - 接着使用新的一个指针
p
,p
开始为0
,接着p
和slow
同步前行,直到两个指针相遇,相遇点即为入环的第一个结点,也是我们想要找的重复数字。
class Solution { public: int findDuplicate(vector & nums) { int lo = 0, hi = 0; do { //一定有环 lo = nums[lo]; //lo = lo->next; hi = nums[nums[hi]]; //hi = hi->next->next; } while (lo != hi); int p = 0; while (p != lo) { //寻找入环的第一个结点 p = nums[p]; lo = nums[lo]; } return lo; }};
执行效率如下:
执行用时:16 ms, 在所有 C++ 提交中击败了86.73% 的用户内存消耗:11.1 MB, 在所有 C++ 提交中击败了34.57% 的用户
转载地址:https://memcpy0.blog.csdn.net/article/details/110091434 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!