❓ 剑指 Offer 03. 数组中重复的数字
难度:简单
找出数组中重复的数字。
在一个长度为 n
的数组 nums
里的所有数字都在 0~n-1
的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
示例 1:
输入:
[2, 3, 1, 0, 2, 5, 3]
输出:2 或 3
限制:
2 < = n < = 100000 2 <= n <= 100000 2<=n<=100000
💡思路:
由于nums
中所有的数字都在 0 ~ n-1
中,所以可以定义一个长度为 n
的数组cnt
:
- 初始化
cnt
为0
; - 遍历
nums
:- 若
cnt[nums[i]]
等于0,则 +1; - 若
cnt[nums[i]]
等于1,则找到重复的数为nums[i]
;
- 若
🍁代码:(C++、Java)
C++
class Solution {
public:
int findRepeatNumber(vector<int>& nums) {
vector<int> cnt(nums.size());
for(int num : nums){
if(cnt[num] == 0) cnt[num]++;
else return num;
}
return -1;
}
};
Java
class Solution {
public int findRepeatNumber(int[] nums) {
int[] cnt = new int[nums.length];
for(int num : nums){
if(cnt[num] == 0) cnt[num]++;
else return num;
}
return -1;
}
}
🚀 运行结果:
🕔 复杂度分析:
-
时间复杂度:
O
(
n
)
O(n)
O(n),其中
n
为数组nums
的长度。 - 空间复杂度: O ( n ) O(n) O(n)。
题目来源:力扣。文章来源:https://www.toymoban.com/news/detail-597154.html
放弃一件事很容易,每天能坚持一件事一定很酷,一起每日一题吧!
关注我LeetCode主页 / CSDN—力扣专栏,每日更新!文章来源地址https://www.toymoban.com/news/detail-597154.html
注: 如有不足,欢迎指正!
到了这里,关于(数组与矩阵) 剑指 Offer 03. 数组中重复的数字 ——【Leetcode每日一题】的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!