[Leetcode] Contains Duplicate 包含重復

rozbo 發布于2019-08-14 12:28 / 1926人閱讀

摘要：代碼集合法復雜度時間空間思路同樣使用集合，但這次我們要維護集合的大小不超過，相當于是記錄一個寬度為的窗口中出現過的數字。

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

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

轉載請注明本文地址：http://specialneedsforspecialkids.com/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