LC-220. 存在重复元素 III(滑动窗口+二分,桶排序)
admin
2024-03-08 21:11:40
0次

220. 存在重复元素 III

难度困难666

给你一个整数数组 nums 和两个整数 k 和 t 。请你判断是否存在 两个不同下标 i 和 j,使得 abs(nums[i] - nums[j]) <= t ,同时又满足 abs(i - j) <= k 。

如果存在则返回 true,不存在返回 false。

示例 1:

输入:nums = [1,2,3,1], k = 3, t = 0
输出:true

示例 2:

输入:nums = [1,0,1,1], k = 1, t = 2
输出:true

示例 3:

输入:nums = [1,5,9,1,5,9], k = 2, t = 3
输出:false

提示:

  • 0 <= nums.length <= 2 * 104
  • -231 <= nums[i] <= 231 - 1
  • 0 <= k <= 104
  • 0 <= t <= 231 - 1

滑动窗口+二分法

题解:https://leetcode.cn/problems/contains-duplicate-iii/solution/gong-shui-san-xie-yi-ti-shuang-jie-hua-d-dlnv/

class Solution {public boolean containsNearbyAlmostDuplicate(int[] nums, int indexDiff, int valueDiff) {int n = nums.length;//使用TreeSet,快速找到 小于等于x的最大值floor 或 小于等于x的最小值ceilingTreeSet set = new TreeSet<>();for(int i = 0; i < n; i++){Long num = nums[i] * 1L;Long l = set.floor(num); //找到小于等于num的最大值Long r = set.ceiling(num); // 找到大于等于num的最小值if(l != null && num-l <= valueDiff) return true;if(r != null && r-num <= valueDiff) return true;set.add(num);// 一个窗口内不可能存在两个大小相同的数,所以可以直接删除// 假设两个数下标是i和j(i < j),当遍历到j时,就会直接返回true了if(i >= indexDiff) set.remove(nums[i-indexDiff]*1L);}return false;}
}// 到i位置检查i-k位置上的元素是否满足要求,超时
// class Solution {
//     public boolean containsNearbyAlmostDuplicate(int[] nums, int indexDiff, int valueDiff) {
//         Set set = new HashSet<>();
//         Map map = new HashMap<>();//nums[i] i
//         for(int i = 0; i < nums.length; i++){
//             if(i > indexDiff) set.remove(nums[i-indexDiff-1]);
//             for(int key : set){
//                 if(Math.abs(nums[i]-key) <= valueDiff && Math.abs(map.get(key) - i) <= indexDiff){
//                     return true;
//                 }
//             }
//             set.add(nums[i]);
//             map.put(nums[i],i);
//         }
//         return false;
//     }
// }

桶排序

题解:https://leetcode.cn/problems/contains-duplicate-iii/solution/gong-shui-san-xie-yi-ti-shuang-jie-hua-d-dlnv/

上述解法无法做到线性的原因是:我们需要在大小为 k 的滑动窗口所在的「有序集合」中找到与 u 接近的数。

如果我们能够将 k 个数字分到 k 个桶的话,那么我们就能 O(1) 的复杂度确定是否有 [u - t, u + t]的数字(检查目标桶是否有元素)。

具体的做法为:令桶的大小为 size=t+1size = t + 1size=t+1,根据 u 计算所在桶编号:

  • 如果已经存在该桶,说明前面已有 [u - t, u + t]范围的数字,返回 true
  • 如果不存在该桶,则检查相邻两个桶的元素是有 [u - t, u + t] 范围的数字,如有 返回 true
  • 建立目标桶,并删除下标范围不在 [max(0, i - k), i) 内的桶
class Solution {long size;public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {int n = nums.length;Map map = new HashMap<>();size = t + 1L;for (int i = 0; i < n; i++) {long u = nums[i] * 1L;long idx = getIdx(u);// 目标桶已存在(桶不为空),说明前面已有 [u - t, u + t] 范围的数字if (map.containsKey(idx)) return true;// 检查相邻的桶long l = idx - 1, r = idx + 1;if (map.containsKey(l) && u - map.get(l) <= t) return true;if (map.containsKey(r) && map.get(r) - u <= t) return true;// 建立目标桶map.put(idx, u);// 移除下标范围不在 [max(0, i - k), i) 内的桶if (i >= k) map.remove(getIdx(nums[i - k] * 1L));}return false;}long getIdx(long u) {return u >= 0 ? u / size : ((u + 1) / size) - 1;}
}

getIdx部分的解释:宫水三叶

相关内容

热门资讯

蜻蜓订购APP贵金属订购非法期...   蜻蜓订购APP以"投资平台"名义对外宣传,主打贵金属期货(订购)交易。该平台一方面强调自身"正规...
悟空订购APP非法期货交易欺骗...   近期,有投资者反映,“悟空订购APP”等平台以白银、贵金属订购为名,宣传所谓“高收益”“低门槛”...
小赢淘金APP期货投资骗局,平...   “小赢淘金”之流,最擅长的就是用“注册送现金”、“充值返券”的糖衣炮弹来引流。别天真地以为那是福...
八方淘金APP非法期货交易欺骗...   警惕!八方生财、每日淘金、小赢淘金、悟空订购、蜻蜓订购、斗金订购等APP均涉嫌非法期货交易!  ...
智易购APP贵金属订购交易骗局...   很多人看到“3元起投”“充值送福利”“操作简单”“随时提现”这类宣传,很容易把智易购APP当成普...
喜玛银庄APP商品订购投资骗局...   喜玛银庄APP白银、铂金“现货订购”骗局警示:无资质平台涉嫌非法期货交易,投资者爆仓后如何维权?...
吉鑫乐享APP炒贵金属订购交易...   近期,多名投资者反映在“吉鑫乐享APP”进行贵金属投资时遭遇严重亏损,甚至血本无归。看似正规的“...
易掘金APP虚假期货投资骗局,...   “易掘金”的APP它打着“高收益、灵活投资”的旗号,宣称通过“商品订购”就能轻松赚钱,吸引了不少...
在大吉订购APP订购交易亏损被...   近期,不少投资者反映在“大吉订购App”上投资白银、铂金等商品遭遇严重亏损。该平台宣称提供现货订...
铂银壹号APP商品订购交易亏损...   许多中小投资者误以为网上的“商品现货订购”是合规合法的理财渠道,殊不知这背后隐藏着巨大的合规风险...
兴鑫淘金APP贵金属订购交易亏...   白银、贵金属或其他商品类投资,除国家批准的正规期货交易场所及持牌期货公司外,市面上大量第三方交易...
铂银掘金APP无资质的违规平台...   铂银掘金等平台的投资者,往往是被“注册送现金”“充值返现券”“首单免亏”等广告话术吸引,进而下载...
八方淘金APP订购交易不合规,...   “八方淘金APP”“铂银掘金APP”“铂银壹号APP”等软件被指以“现货订购”为名,实际采用高杠...
在指尖订购APP订购商品亏损被...   指尖订购APP这类平台,表面是“订购交易”,实则是披着电商外衣的非法期货陷阱。绝大多数投资者被蒙...
在犀贝易购APP做商品订购交易...   市面上打着“现货投资”“贵金属交易”旗号的APP并不少,但真正合规、受监管的平台并不多。犀贝易购...
易达淘金APP虚假商品订购交易...   易达淘金APP存在严重的虚假宣传与违规交易行为。该平台打着“商品订购”的旗号,实则通过不合规的交...
大浪淘金APP白银订购亏损被骗...   大浪淘金APP最隐蔽的套路,在于其完全封闭的内盘交易系统。表面上,它宣称与国际贵金属市场接轨;实...
一品好购APP上订购白银出现亏...   一品好购APP原名“一品订购”,运营方为上海宝智未来信息技术有限公司。近期不少投资者反映在该平台...
九州订购APP贵金属订购投资骗...   九州订购APP正通过抖.音、快手、今日头条等平台大量投放投资广告,用“5元起投”“充值返现”“0...
坚锅淘金APP交易软件并不正规...   当前,市面上大量所谓的“现货商城订购”交易软件,早已偏离了正常的实物商品买卖,演变为高杠杆、高手...