Given an array of integers, find out whether there are two distinct indices i and j in the array such that the difference between nums[i] and nums[j] is at most t and the difference between i and j is at most k.
[balabala] 我的思路是构造一个类,其包含两个属性:值和下标。首先将原始数组转换为包装类数组,接着排序包装类数组,然后遍历有序数组检查是否有满足题意的pair。实现如Method1, 在不使用long的情况下需要对溢出做容错处理。 Method2 为网上大牛的思路(http://blog.csdn.net/xudli/article/details/46323247),很开心认识TreeSet,自己之前从没用过……
import java.util.SortedSet; public class Solution { // Method2: 滑动窗口 + TreeSet public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) { if (nums == null || nums.length < 2 || k < 1 || t < 0) return false; SortedSet<Long> set = new TreeSet<Long>(); for (int i = 0; i < nums.length; i++) { SortedSet<Long> subset = set.subSet((long)nums[i] - t, (long)nums[i] + t + 1); if (!subset.isEmpty()) return true; if (i >= k) set.remove((long)nums[i - k]); set.add((long)nums[i]); } return false; } // Method 1 class WrappedNum{ int value; int idx; public WrappedNum(int value, int idx) { this.value = value; this.idx = idx; } } class WrappedNumComparator implements Comparator { @Override public int compare(Object o1, Object o2) { int value1 = ((WrappedNum)o1).value; int value2 = ((WrappedNum)o2).value; if (value1 > 0 && value2 > 0 || (value1 < 0 && value2 < 0)) return value1 - value2; else if (value1 > 0) return 1; else return -1; } } public boolean containsNearbyAlmostDuplicate1(int[] nums, int k, int t) { if (nums == null || nums.length < 2) return false; WrappedNum[] numsWrapped = new WrappedNum[nums.length]; for (int i = 0; i < nums.length; i++) { numsWrapped[i] = new WrappedNum(nums[i], i); } Arrays.sort(numsWrapped, new WrappedNumComparator()); for (int i = 1; i < nums.length; i++) { int currValue = numsWrapped[i].value; for (int j = i - 1; j >= 0 && (currValue - numsWrapped[j].value) >= 0 && (currValue - numsWrapped[j].value) <= t; j--) { if ((Math.abs(numsWrapped[i].idx - numsWrapped[j].idx)) <= k) { return true; } } } return false; } }
相关推荐
python python_leetcode题解之220_Contains_Duplicate_III.py
java入门 java_leetcode题解之219_Contains_Duplicate_II
python python_leetcode题解之217_Contains_Duplicate.py
python python_leetcode题解之219_Contains_Duplicate_II.py
contains-duplicate-0217 find-minimum-in-rotated-sorted-array-0153 数组的乘积-除了-self-0238 从排序数组中删除重复项-0026 搜索旋转排序数组-0033 两个整数之和-0371 二和-0001 回溯 组合-和-0039 组合总和-ii-...
java lru leetcode leetcode-java leetcode刷题笔记 已做题目列表 1.Two Sum 3.Longest Substring Without Repeating Characters ...III ...217.Contains Duplicate 263.Ugly Number 264.Ugly Number II
Leetcode的ac是什么意思 LeetCodeInJava List #98 Validate Binary Search Tree #100 Same Tree #104 Maximum Depth of Binary Tree #122 Best Time to Buy and Sell Stock II #136 Single Number #150 Evaluate ...
“contains_duplicate.py” - 检查整数列表是否包含任何重复项的快速算法。 “contains_nearby_duplicate.py” - 检查整数列表是否包含距离 k 内的任何重复项的快速算法。 "coin_arrangement.py" - 给定 n,算法找到...
leetcode 浇花力扣解决方案 简单的 #0001 - Two Sum #0007 - Reverse Integer #0009 - Palindrome Number #0035 - Search Insert Position #0058 - Length of Last Word #0066 - Plus One #0083 - Remove Duplicates...
260 | [Single Number III](https://leetcode.com/problems/single-number-iii/) | [C++](./C++/single-number-iii.cpp) [Python](./Python/single-number-iii.py) | _O(n)_ | _O(1)_ | Medium || 268| [Missing ...
leetcode下载 algorithm_reearch algorithm_reearch 链表 leetcode: 146 有无环 双向链表,删除 写大于读的情形 LinkedHashMap与 LRU算法 基于访问时间的链表 或者 基于插入时间的链表 哈希表: leetcode: 1. two sum...
Contains Duplicate (E) 48. Rotate Image (M) -> 2 73. Set Matrix Zeroes (M) 1. Two Sum (E) 167. Two Sum II - Input array is sorted (E) 653. Two Sum IV - Input is a BST (E) -> 2 26. Remove Duplicates ...
哈希表在解决两数之和、查找重复元素(Contains Duplicate)等问题时发挥关键作用。 二、高级数据结构 1. 树:二叉树、平衡二叉树(AVL、红黑树)、堆(优先队列)等都是重要的树形结构。例如,二叉搜索树、最小...
leetcode 答案Leet Code 挑战 这是我提交给 Lambda School CS Unit 2 构建周的已接受 ...Duplicates](https://leetcode.com/problems/contains-duplicate/) [x] [Linked List Cycle II](https://leetcode.co
leetcode leetcode_java prepare for jobhunting. java version of Leetcode. easy 55 about takes 5 days medium 112 about takes 20 days hard 48 about take 10 days Summarize and implement all sort ...
题目217——存在重复元素(Contains Duplicate): 这道题目要求我们检查给定的整数数组`nums`中是否存在重复的元素。如果存在重复元素,函数应返回`true`,否则返回`false`。 **解决方案一:哈希表(Hash Table)*...
- 哈希表在解决"数组中的重复元素"(Contains Duplicate)等问题中起到关键作用,提供了快速查找和去重的能力。 10. **位运算和整数操作** - 例如"不同位的数字对的数量"(Number of 1 Bits)和"翻转二进制位"...
在给定的代码片段中,我们讨论了一个名为“手稿_V1.22”的文件,该文件涉及到在C++中解决LeetCode上的一个问题——“Contains Duplicate II”(问题编号219)。这个问题要求我们判断一个整数数组`nums`中是否存在两...
- **Contains Duplicate**:检查数组中是否存在重复的元素。哈希表可以用于跟踪已遇到的元素。 - **Jewels and Stones**:计算在给定的字符集合(jewels)中,有多少字符出现在另一个字符集合(stones)中。哈希表...