文档章节

Contains Duplicate III

Finley.Hamilton
 Finley.Hamilton
发布于 2015/08/12 16:15
字数 433
阅读 31
收藏 0

题目

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.

We just call nums[i] and nums[j] friend element in this artical

思考

  • A sliding window is must

  • use a Binary Search Tree to store the element inside the window

  • search/insert/remove O(logK) in window

every time we move window by one step, we check the newest element: Does it has some friend element?

It is a search problem, you need to find element in the tree, since BST can provide good search performance. It is ok.

Code

import java.util.*;

/**
 * Created by zuo on 15-8-12.
 */
public class ContainsDuplicatedIII {

    /**
     *
     * @param nums
     * @param k index diff, means the window can have k+1 element
     * @param t value diff
     * @return
     */
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        if ( k <= 0 || t < 0) {
            return false;
        }
        // the window start (included)
        int winStart = 0;
        // the window ends (included)
        int winEnd = 0;

        TreeMap<Integer, Set<Integer>> tree = new TreeMap<Integer, Set<Integer>>();

        /**
         * cauz winEnd should be included, initialize the window
         */
        if (!tree.containsKey(nums[winEnd])) {
            tree.put(nums[winEnd], new HashSet<Integer>());
        }
        tree.get(nums[winEnd]).add(winEnd);

        while(winEnd < nums.length) {

            /**
             * reach criterion exception himself
             */
            Map.Entry<Integer, Set<Integer>> ceilingEntry = tree.ceilingEntry(nums[winEnd] - t);
            Map.Entry<Integer, Set<Integer>> floorEntry = tree.floorEntry(nums[winEnd] + t);
            if ((ceilingEntry != null && (ceilingEntry.getKey() != nums[winEnd] || ceilingEntry.getValue().size() > 1) ) || (floorEntry != null && (floorEntry.getValue().size() > 1 || floorEntry.getKey() != nums[winEnd]))) {
                return true;
            }

            /**
             * ready for next epoch
             * now the window has (winEnd - winStart + 1) elements(window size = element count)
             * winStart++ if the window reach biggest
             */
            winEnd++;
            if (winEnd == nums.length) {
                break;
            }
            if (!tree.containsKey(nums[winEnd])) {
                tree.put(nums[winEnd], new HashSet<Integer>());
            }
            tree.get(nums[winEnd]).add(winEnd);
            if (winEnd - winStart > k) {
                if (tree.containsKey(nums[winStart])) {
                    tree.get(nums[winStart]).remove(winStart);
                    if (tree.get(nums[winStart]).size() == 0) {
                        tree.remove(nums[winStart]);
                    }
                }
                winStart++;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        ContainsDuplicatedIII containsDuplicatedIII = new ContainsDuplicatedIII();
        System.out.println(containsDuplicatedIII.containsNearbyAlmostDuplicate(new int[]{1, 3 ,1 }, 1, 1));//f
        System.out.println(containsDuplicatedIII.containsNearbyAlmostDuplicate(new int[]{1, 2}, 1, -1));//f
        System.out.println(containsDuplicatedIII.containsNearbyAlmostDuplicate(new int[]{1}, 1, 1));//f
        System.out.println(containsDuplicatedIII.containsNearbyAlmostDuplicate(new int[]{1,2,3,4,5}, 1,3)); //t
        System.out.println(containsDuplicatedIII.containsNearbyAlmostDuplicate(new int[]{1,3,5,3,1}, 1,3));//t
        System.out.println(containsDuplicatedIII.containsNearbyAlmostDuplicate(new int[]{1,1,1}, 1,0));//t
        System.out.println(containsDuplicatedIII.containsNearbyAlmostDuplicate(new int[]{1,2,3}, 1,0));//f
        System.out.println(containsDuplicatedIII.containsNearbyAlmostDuplicate(new int[]{1,1,1}, 0,1));//f
        System.out.println(containsDuplicatedIII.containsNearbyAlmostDuplicate(new int[]{ -1 , - 1}, 1, 0));//t`
        System.out.println(containsDuplicatedIII.containsNearbyAlmostDuplicate(new int[]{ 1,3,1}, 2, 1));//t
        System.out.println(containsDuplicatedIII.containsNearbyAlmostDuplicate(new int[]{ 4,1,6,3}, 100, 1));//t
    }
}

© 著作权归作者所有

共有 人打赏支持
Finley.Hamilton

Finley.Hamilton

粉丝 5
博文 45
码字总数 15431
作品 0
广州
私信 提问
LeetCode Contains Duplicate

LeetCode Contains Duplicate Mz的博客2016-03-15173 阅读 算法C/C++ Contains Duplicate 原题传送门: https://leetcode.com/problems/contains-duplicate/ Contains Duplicate II 原题传送门......

Mz的博客
2016/03/15
0
0
Percona Server 5.1.65-14.0 发布

Percona 5.1系列的分支5.1.65-14.0发布。2012-09-03.上一个版本是2012-05-25的5.1.63.不想升级到5.5的用户可以使用此版本。 完全改进包括: Percona is glad to announce the release of Per...

fei
2012/09/05
753
0
Leetcode 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 the absolute difference between nums[i] and nums[j] is at most t and t......

ShutLove
2017/11/29
0
0
LeetCode:Contains Duplicate II - 判断数组内是否有重复元素2

1、题目名称 Contains Duplicate II(判断数组内是否有重复元素2) 2、题目地址 https://leetcode.com/problems/contains-duplicate-ii/ 3、题目内容 英文:Given an array of integers and ...

北风其凉
2015/10/15
2.7K
0
217. Contains Duplicate - LeetCode

Question 217. Contains Duplicate Solution 题目大意:判断数组中是否有重复元素 思路:构造一个set,不重复就加进去,重复返回true,如果数据量大的话,可以用布隆过滤器 Java实现:...

yysue
2018/07/18
0
0

没有更多内容

加载失败,请刷新页面

加载更多

泛型就这么简单

前言 从今天开始进入Java基础的复习,可能一个星期会有一篇的<十道简单算法>,我写博文的未必都是正确的~如果有写错的地方请大家多多包涵并指正~ 今天要复习的是泛型,泛型在Java中也是个很...

群星纪元
35分钟前
3
0
大数据提醒你:中国这些古建筑,可能是下一个巴黎圣母院!

大家晚上好,我是今天的提笔人嗅嗅。 巴黎圣母院失火事件让我的心情很沉重,一句无关痛痒的安慰“巴黎不哭”,已经不能表达我对这场文化之殇的惋惜之痛,人类伟大的建筑在一瞬间被毁灭。 世界...

forespider
46分钟前
0
0
mysql函数substring_index的用法

substring_index 按索引字符位进行截取字符串 substring_index(“待截取的字符串”,“截取数据依据的字符”,截取字符的位置N) 第三个参数可正,可负。正数表示索引字符前面的字符串,负数...

echojson
46分钟前
2
0
好程序员web前端分享用CSS和JS打造一个简单的图片编辑器

好程序员web前端分享用CSS和JS打造一个简单的图片编辑器,本文主要是利用CSS的 filter和简单的Jquery代码来实现一个简单的图片编辑器,包括对图片的透明度,黑白,图片亮度等调节。 CSS filt...

好程序员IT
56分钟前
2
0
浅析spring mvc的细节

spring mvc 整体结构 系统监听到请求 -> 通知tomcat -> 根据web.xml 通知相应的拦截器(spring mvc 通常指DispatcherServlet) --> 检查url是否有相匹配的请求实现 --> 拿到请求实现bean的适配...

最爱肉肉
58分钟前
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部