Contains Duplicate III (M)
題目
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
題意
判斷陣列中是否存在這樣一組數，它們的值之差的絕對值不大于t，且下標之差的絕對值不大于k，
思路
最簡單的方法是直接遍歷，再判斷當前數與它之后的k個數的差值是否符合條件，
優化的方法是借助紅黑樹實作滑動視窗思想：在紅黑樹中只保存k+1個連續的數(這樣就控制了樹中所有數的下標差不大于k)，每次加入新數時，先去除一個數(容量已到達k+1的情況下)，在樹中找到小于新數的最大數和大于新數的最小數，判斷它們與新數的差是否滿足條件，最后將新數加入紅黑樹中，
代碼實作
Java
暴力法
class Solution {
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
if (t < 0) {
return false;
}
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j <= Math.min(i + k, nums.length - 1); j++) {
// 不轉化為long可能會有溢位
if (Math.abs((long) nums[i] - (long) nums[j]) <= (long) t) {
return true;
}
}
}
return false;
}
}
紅黑樹
class Solution {
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
if (t < 0) {
return false;
}
TreeSet<Integer> set = new TreeSet<>();
for (int i = 0; i < nums.length; i++) {
// 保證樹的容量始終不超過k+1
if (i > k) {
set.remove(nums[i - k - 1]);
}
if (set.contains(nums[i])) {
return true;
}
// 因為可能為null，所以必須用包裝類接收
Integer lower = set.lower(nums[i]);
Integer higher = set.higher(nums[i]);
// 轉換成long計算防止溢位
if (lower != null && (long) nums[i] - lower <= t
|| higher != null && (long) higher - nums[i] <= t) {
return true;
}
set.add(nums[i]);
}
return false;
}
}
JavaScript
暴力法
/**
* @param {number[]} nums
* @param {number} k
* @param {number} t
* @return {boolean}
*/
var containsNearbyAlmostDuplicate = function (nums, k, t) {
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j <= i + k && j < nums.length; j++) {
if (Math.abs(nums[j] - nums[i]) <= t) {
return true
}
}
}
return false
}
參考
very simple and clean solution on Java (72.47%)
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/143958.html
標籤：其他