剑指 Offer 03 - 数组中重复的数字
# 📃 题目描述
题目链接:剑指 Offer 03. 数组中重复的数字 (opens new window)
# 🔔 解题思路
利用数据结构特点,容易想到使用哈希表(Set)记录数组的各个数字,当查找到重复数字则直接返回,这里就不贴代码了
题目说明在一个长度为 n 的数组 nums 里的所有数字都在 0 ~ n-1 的范围内 。 此说明含义:数组元素的 索引 和 值 是 一对多 的关系。
因此,可遍历数组并通过交换操作,使元素的 索引 与 值 一一对应(即 nums[i] = inums[i]=i )。因而,就能通过索引映射对应的值,起到与字典等价的作用。
class Solution {
public int findRepeatNumber(int[] nums) {
int i = 0;
while (i < nums.length) {
int targetIndex = nums[i];
// 当前 nums[i] 出现在正确的位置
if (targetIndex == i) {
i ++;
}
else if (nums[targetIndex] != nums[i]) {
swap(nums, i, targetIndex);
}
// nums[targetIndex] == nums[i], 重复数字
else {
return nums[i];
}
}
return -1;
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
# 💥 复杂度分析
- 空间复杂度:
- 时间复杂度:
🎁 公众号

各位小伙伴大家好呀,叫我小牛肉就行,目前在读东南大学硕士,上方扫码关注公众号「飞天小牛肉」,与你分享我的成长历程与技术感悟~
帮助小牛肉改善此页面 (opens new window)
Last Updated: 2023/02/16, 11:27:10