☆打卡算法☆LeetCode 219. 存在重复元素 II 算法解析
☆打卡算法☆LeetCode 219. 存在重复元素 II 算法解析
恬静的小魔龙
发布于 2022-09-27 09:42:08
发布于 2022-09-27 09:42:08
文章被收录于专栏：Unity3D
大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。
一、题目
1、算法题目
“给定一个整数数组和一个整数k，判断数组中是否存在连个不同的索引，返回两个索引对应的数组的值相同是否存在。”
题目链接：
来源：力扣（LeetCode）
链接： 219. 存在重复元素 II - 力扣（LeetCode）
2、题目描述
给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个 不同的索引 i 和 j ，满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false 。
示例 1：
输入： nums = [1,2,3,1], k = 3
输出： true示例 2：
输入： nums = [1,0,1,1], k = 1
输出： true二、解题
1、思路分析
本题要要判断在整数数组中是否有满足条件 nums[i] == nums[j] 且 abs(i - j) <= k 的数。
遍历数组nums，不断的判断下标 j < i 使得 nums[i] == nums[j]，且当i-j≤k时，就找到了符合题意的i和j。
如果要满足题意i-j≤k，那么在下标i之前存在于nums[i]相等的元素，应该先找到最大的下标j，判断i-j≤k是否成立。
用哈希表记录每个元素的最大下标，遍历数组：
- 如果哈希表中存在和nums[i]相等的元素且该元素在哈希表中记录的下标j满足i-j≤k，则返回true
- 将nums[i]和下标i存入哈希表，此时i是nums[i]的最大下标
重复以上操作，当遍历结束没有遇到两个相等元素的下标差的绝对值不超过k，则返回false。
2、代码实现
代码参考：
class Solution {
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) {
return 0;
}
int nr = grid.length;
int nc = grid[0].length;
int num_islands = 0;
for (int r = 0; r < nr; ++r) {
for (int c = 0; c < nc; ++c) {
if (grid[r][c] == '1') {
++num_islands;
grid[r][c] = '0';
Queue<Integer> neighbors = new LinkedList<>();
neighbors.add(r * nc + c);
while (!neighbors.isEmpty()) {
int id = neighbors.remove();
int row = id / nc;
int col = id % nc;
if (row - 1 >= 0 && grid[row-1][col] == '1') {
neighbors.add((row-1) * nc + col);
grid[row-1][col] = '0';
}
if (row + 1 < nr && grid[row+1][col] == '1') {
neighbors.add((row+1) * nc + col);
grid[row+1][col] = '0';
}
if (col - 1 >= 0 && grid[row][col-1] == '1') {
neighbors.add(row * nc + col-1);
grid[row][col-1] = '0';
}
if (col + 1 < nc && grid[row][col+1] == '1') {
neighbors.add(row * nc + col+1);
grid[row][col+1] = '0';
}
}
}
}
}
return num_islands;
}
}
3、时间复杂度
时间复杂度：O(n)
其中n是数组nums的长度，需要遍历数组一次，对于每个元素，哈希表的操作时间都是O(n)。
空间复杂度：O(n)
其中n是数组nums的长度，需要用哈希表来记录每个元素的最大下标，哈希表中的元素个数不会超过n。
三、总结
维护一个哈希表。
哈希表里面时钟最多包含k个元素，出现重复值则说明在k的区间内存在重复元素。
每次遍历一个元素则将钙元素加入哈希表汇总，如果哈希表的大小大于k，则移除最前面的数字。
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2022-08-26，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
