[Leetcode] Contains Duplicate 包含重复

rozbo 发布于2019-08-14 12:28 / 1843人阅读

摘要：代码集合法复杂度时间空间思路同样使用集合，但这次我们要维护集合的大小不超过，相当于是记录一个宽度为的窗口中出现过的数字。

Contains Duplicate I

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 if every element is distinct.

集合法 复杂度

时间 O(N) 空间 O(N)

思路

用一个集合记录之前遇到过的数字，如果新的数字已经在集合中出现过了，则说明有重复。

代码

public class Solution {
    public boolean containsDuplicate(int[] nums) {
        Set set = new HashSet();
        for(int i = 0; i < nums.length; i++){
            if(set.contains(nums[i])) return true;
            set.add(nums[i]);
        }
        return false;
    }
}

Contains Duplicate II

Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the difference between i and j is at most k.

集合法 复杂度

时间 O(N) 空间 O(K)

思路

同样使用集合，但这次我们要维护集合的大小不超过k，相当于是记录一个宽度为k的窗口中出现过的数字。

代码

public class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        Set set = new HashSet();
        for(int i = 0; i < nums.length; i++){
            if(set.contains(nums[i])) return true;
            set.add(nums[i]);
            if(set.size()>k) set.remove(nums[i-k]);
        }
        return false;
    }
}

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 difference between nums[i] and nums[j] is at most t and the difference between i and j is at most k.

二叉搜索树 复杂度

时间 O(NlogK) 空间 O(K)

思路

要求判断之前是否存在差值小于t的数字，我们需要知道在当前数字x两边的数字，即最大的小于x的数字和最小的大于x的数字。二叉搜索树有也有这样的性质，它的左子树的最右节点是最大的较小值，右子树的最左节点是最小的较大值。这里我们用TreeSet这个类，它实现了红黑树，并有集合的性质，非常适合这题。我们同样也是维护一个大小为k的TreeSet，多余k个元素时把最早加入的给删除。用ceiling()和floor()可以找到最小的较大值和最大的较小值。

代码

public class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        TreeSet set = new TreeSet();
        for(int i = 0; i < nums.length; i++){
            int x = nums[i];
            // 最大的小于x的数字
            if(set.ceiling(x) != null && set.ceiling(x) <= t + x) return true;
            // 最小的大于x的数字
            if(set.floor(x) != null && x <= t + set.floor(x)) return true;
            set.add(x);
            if(set.size()>k) set.remove(nums[i-k]);
        }
        return false;
    }
}

云服务器 GPU云服务器重复包含 php 重复包含 Contains DUPLICATE

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/64497.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 217 Contains Duplicate

摘要：题目详情输入一个整数的数组，如果数组中的元素有重复的，那么返回，如果数组中的元素都是唯一的，那么返回思路这道题理解起来比较简单，首先还是要注意一下边界条件异常输入，对于长度小于等于的数组做一个直接的返回对于这种要考虑数组中元素的重复的问题，题目详情 Given an array of integers, find if the array contains any duplicate...

philadelphia 2019-08-15 13:53 评论0 收藏0
Leetcode PHP题解--D90 217. Contains Duplicate

摘要：题目链接题目分析返回给定的数组中是否有元素重复出现。思路用和即可最终代码若觉得本文章对你有用，欢迎用爱发电资助。 D90 217. Contains Duplicate 题目链接 217. Contains Duplicate 题目分析返回给定的数组中是否有元素重复出现。思路用count和array_unique即可最终代码

mingde 2019-07-01 14:01 评论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
[LintCode/LeetCode] Contains Duplicate II

Problem Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the absolute difference between i and j is at ...

894974231 2019-08-19 10:48 评论0 收藏0