内容简介:Given an array of integers, find out whether there are two distinct indices i and j in the array such that the absolute difference between nums[i] and nums[j] is at most t and the absolute difference between i and j is at most k.Example 1:Example 2:
Given an array of integers, find out whether there are two distinct indices i and j in the array such that the absolute difference between nums[i] and nums[j] is at most t and the absolute difference between i and j is at most k.
Example 1:
Input: nums = [1,2,3,1], k = 3, t = 0 Output: true
Example 2:
Input: nums = [1,0,1,1], k = 1, t = 2 Output: true
Example 3:
Input: nums = [1,5,9,1,5,9], k = 2, t = 3 Output: false
难度:medium
题目:给定一整数数组,找出是否存在两个不同的索引i, j使其索引差的绝对值小于等于k, 值的差的绝对值小于等于t.
思路:
- 暴力破解,
- 使用滑动窗口和TreeSet是为了使得滑动窗口有序,TreeSet底层是二叉搜索树, 如果暴力破解时间复杂度为O(kn), 改用TreeSet使得搜索时间复杂度为O(log K), 故总的时间复杂度为O(nlog K)。
Runtime: 22 ms, faster than 70.38% of Java online submissions for Contains Duplicate III.
Memory Usage: 40.4 MB, less than 5.58% of Java online submissions for Contains Duplicate III.
class Solution { public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) { if(nums == null || nums.length < 2 || k < 1 || t < 0){ return false; } TreeSet<Long> treeSet = new TreeSet<>(); for (int i = 0; i < nums.length; i++) { if (!treeSet.subSet((long) nums[i] - t, true, (long) nums[i] + t, true).isEmpty()) { return true; } if (i >= k) { treeSet.remove((long) nums[i - k]); } treeSet.add((long) nums[i]); } return false; } }
Runtime: 987 ms, faster than 5.06% of Java online submissions for Contains Duplicate III.
Memory Usage: 38.8 MB, less than 56.75% of Java online submissions for Contains Duplicate III.
class Solution { public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) { for (int i = 0; i < nums.length; i++) { for (int j = i + 1; j < Math.min(nums.length, i + k + 1); j++) { if (nums[i] > 0 && nums[j] < 0 || nums[i] < 0 && nums[j] > 0) { if (Math.abs(nums[i]) - t > 0 || Math.abs(nums[i]) - t + Math.abs(nums[j]) > 0) { continue; } } if (Math.abs(nums[i] - nums[j]) <= t) { return true; } } } return false; } }
以上所述就是小编给大家介绍的《220. Contains Duplicate III》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
深入浅出 MFC 第二版
侯俊杰 / 松岗 / 1997.05
深入浅出MFC是一本介绍 MFC(Microsoft Foundation Classes)程式设计技术的书籍。对於 Windows 应用软体的开发感到兴趣,并欲使用 Visual C++ 整合环境的视觉开发工具,以 MFC 为程式基础的人,都可以从此书获得最根本最重要的知识与实例。 如果你是一位对 Application Framework 和物件导向(Object Orien......一起来看看 《深入浅出 MFC 第二版》 这本书的介绍吧!