220. Contains Duplicates

stonezhu 發布于2019-08-14 14:24 / 3107人閱讀

摘要：題目解答這一題有兩個思路，都是參考里寫出來的。是更加直接的用和來看有沒有在這個范圍內存在的數。

題目：
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.

解答：
這一題有兩個思路，都是參考discussion里寫出來的。一個是bucket, 一個是TreeSet。
1.bucket是按照兩個數最多相差t這個性質，把每個數分到不一樣的bucket里，在k范圍內，如果有兩個數在同一個bucket里，那么說明這兩個數滿足條件；或者相鄰的bucket里存在一個數，而且與這個數的差小于等于t，那這個數也滿足；其它都是超出范圍的。

public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
    if (k < 1 || t < 0) return false;
    Map map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        long remappedNum = (long) nums[i] - Integer.MIN_VALUE;
        long bucket = remappedNum / ((long) t + 1);
        if (map.containsKey(bucket) || (map.containsKey(bucket - 1) && remappedNum - map.get(bucket - 1) <= t) || (map.containsKey(bucket + 1) && map.get(bucket + 1) - remappedNum <= t)) {
            return true;
        }
        if (map.entrySet().size() >= k) {
            long lastBucket = ((long) nums[i - k] - Integer.MIN_VALUE) / ((long) t + 1);
            map.remove(lastBucket);
        }
        map.put(bucket, remappedNum);
    }
    return false;
}

2.TreeSet是更加直接的用floor和ceiling來看有沒有在這個范圍內存在的數。

public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
    if (k < 1 || t < 0) return false;
    TreeSet values = new TreeSet(); 
    for (int i = 0; i < nums.length; i++) {
        Integer floor = values.floor(nums[i] + t);
        Integer ceiling = values.ceiling(nums[i] - t);
        if ((floor != null && floor >= nums[i]) || (ceiling != null && ceiling <= nums[i])) {
            return true;
        }
        if (values.size() >= k) {
            values.remove(nums[i - k]);
        }
        values.add(nums[i]);
    }
    return false;
}

云服務器 GPU云服務器 Duplicates Contains 220cdn 企業郵箱220

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/64989.html

leetcode217.219.220 contains duplicate

摘要：輸入一個整數數組，查看數組中是否存在重復的值。新的數組中數組的下標為原數組的值，如果遍歷過，則設置為。這里使用了作為實現的數據結構，通過堆的形式對集合中的數據進行存儲，從而我們可以通過某種順序獲得該集合中的所有順序。 217 Contains Duplicate Given an array of integers, find if the array contains any dup...

tulayang 2019-08-16 10:56 評論0 收藏0
LeetCode 攻略 - 2019 年 7 月上半月匯總（55 題攻略）

摘要：微信公眾號記錄截圖記錄截圖目前關于這塊算法與數據結構的安排前。已攻略返回目錄目前已攻略篇文章。會根據題解以及留言內容，進行補充，并添加上提供題解的小伙伴的昵稱和地址。本許可協議授權之外的使用權限可以從處獲得。 Create by jsliang on 2019-07-15 11:54:45 Recently revised in 2019-07-15 15:25:25 一目錄不...

warmcheng 2019-08-26 10:09 評論0 收藏0
220. Contains Duplicate III

摘要：如果不是，則在相鄰的兩個內再找。如果相鄰的內元素絕對值只差在以內，說明我們知道到了，返回為了保證，我們在時，刪除對應的的元素都會落在里。為了解決這個問題，所有元素橫移。 Given an array of integers, find out whether there are two distinct indices i and j in the array such that th...

王偉廷 2019-08-16 10:36 評論0 收藏0
[LeetCode] Contains Duplicate

Contains Duplicate Given an array of integers, find if the array contains any duplicates. Your function should return true if any value appears at least twice in the array, and it should return false ...

褰辯話 2019-08-19 10:43 評論0 收藏0
[Leetcode] Contains Duplicate 包含重復

摘要：代碼集合法復雜度時間空間思路同樣使用集合，但這次我們要維護集合的大小不超過，相當于是記錄一個寬度為的窗口中出現過的數字。 Contains Duplicate I Given an array of integers, find if the array contains any duplicates. Your function should return true if any v...

rozbo 2019-08-14 12:28 評論0 收藏0