成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

220. Contains Duplicates

stonezhu / 3115人閱讀

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

題目：
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是按照兩個數(shù)最多相差t這個性質(zhì)，把每個數(shù)分到不一樣的bucket里，在k范圍內(nèi)，如果有兩個數(shù)在同一個bucket里，那么說明這兩個數(shù)滿足條件；或者相鄰的bucket里存在一個數(shù)，而且與這個數(shù)的差小于等于t，那這個數(shù)也滿足；其它都是超出范圍的。

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來看有沒有在這個范圍內(nèi)存在的數(shù)。

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;
}

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/64989.html

相關(guān)文章

  • leetcode217.219.220 contains duplicate

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

    tulayang 評論0 收藏0

  • LeetCode 攻略 - 2019 年 7 月上半月匯總（55 題攻略）

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

    warmcheng 評論0 收藏0

  • 220. Contains Duplicate III

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

    王偉廷 評論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 ...

    褰辯話 評論0 收藏0

  • [Leetcode] Contains Duplicate 包含重復(fù)

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

    rozbo 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<