网站建设佰金手指科杰十三,上海有哪些大公司,软件开发定制案例,渭南网站建设费用明细想要精通算法和SQL的成长之路 - 存在重复元素 前言一. 存在重复元素II二. 存在重复元素III2.1 基于红黑树增删改查 前言 想要精通算法和SQL的成长之路 - 系列导航 一. 存在重复元素II
原题链接
思路#xff1a;
我们用HashSet存储元素#xff0c;做到去重的效果。同时存储… 想要精通算法和SQL的成长之路 - 存在重复元素 前言一. 存在重复元素II二. 存在重复元素III2.1 基于红黑树增删改查 前言 想要精通算法和SQL的成长之路 - 系列导航 一. 存在重复元素II
原题链接
思路
我们用HashSet存储元素做到去重的效果。同时存储的元素个数固定在k个。这个HashSet相当于是一个滑动窗口了。那么从左往右遍历不断地往HashSet中塞元素一旦超过容量剔除滑动窗口最左侧元素。set.remove(nums[i - k - 1]);遍历过程中一旦发现当前元素存在于HashSet中直接返回true即可。
代码如下
public boolean containsNearbyDuplicate(int[] nums, int k) {HashSetInteger set new HashSet();for (int i 0; i nums.length; i) {// 滑动窗口只存储k个元素超过了则移除if (i k) {set.remove(nums[i - k - 1]);}if (set.contains(nums[i])) {return true;}set.add(nums[i]);}return false;
}二. 存在重复元素III
原题链接 我们先来一个最简单的思路暴力法
针对每个元素作为滑动窗口的左边界。往后固定indexDiff长度的区间。我们在[leftleftindexDiff] 区间内遍历数组计算差值。如果满足差值 valueDiff 值说明找到满足条件的结果返回true。
但是这种操作有着大量的重复计算而且数组的无规律性在最坏的情况下我们得遍历整个长度为 k 的区间数组。那咋办呢
思路如下
我们可以维护一个有序并且长度为 k 的滑动窗口。那么对于该区间的任意一个数字num。既然要满足差值 valueDiff 值。那么在这个有序的集合当中。哪个数字最满足条件第一种小于等于 num 的最大值。第二种和大于等于num的最小值。即值num左右两侧最靠近的数值是我们想要的。那么对于有序的数组而言想要查找上面两个数用哪种方式最合适二分法。当然我们还需要不断地维护这个滑动窗口对应的数据结构。
2.1 基于红黑树增删改查
下面来自百度百科的相关红黑树介绍
红黑树是一种特化的AVL树平衡二叉树都是在进行插入和删除操作时通过若干次特定操作保持二叉查找树的平衡从而获得较高的查找性能。而这个特定操作对于红黑树而言可以限制到最多三次。它虽然是复杂的但它的最坏情况运行时间也是非常良好的并且在实践中是高效的 它可以在O(log n)时间内做查找插入和删除这里的 n 是树中元素的数目。
针对上面的功能红黑树都具备其查询
查询不超过num的最大值floor函数。注意如果找不到则返回null。查询超过num的最小值ceiling函数。注意如果找不到则返回null。
那么我们就不难写出代码切记对象和基本数据类型的比较要判断null否则会报空指针哦~
// floorNum num ,最大值
Long floorNum tree.floor(num);
// ceilingNum num ,最小值
Long ceilingNum tree.ceiling(num);
if (floorNum ! null num - floorNum valueDiff) {return true;
}
if (ceilingNum ! null ceilingNum - num valueDiff) {return true;
}由于题目的元素值存在以下范围 因此我们在存储的时候要把它转成Long型。最终代码如下
public boolean containsNearbyAlmostDuplicate(int[] nums, int indexDiff, int valueDiff) {TreeSetLong tree new TreeSet();for (int i 0; i nums.length; i) {// int 转 long因为限制问题long num nums[i] * 1L;// floorNum num ,最大值Long floorNum tree.floor(num);// ceilingNum num ,最小值Long ceilingNum tree.ceiling(num);if (floorNum ! null num - floorNum valueDiff) {return true;}if (ceilingNum ! null ceilingNum - num valueDiff) {return true;}tree.add(num);// 超过了滑动窗口大小if (i indexDiff) {tree.remove(nums[i - indexDiff] * 1L);}}return false;
}
