leetcode217.219.220 contains duplicate

tulayang 發布于2019-08-16 10:56 / 1721人閱讀

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

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

輸入一個整數數組，查看數組中是否存在重復的值。

思路一：hashmap or hashset

使用java中的數據結構將已經遍歷起來的值存儲起來，然后查詢當前的值是否已經便利過

    public boolean containsDuplicate(int[] nums) {
        Map map = new HashMap();
        
        for(int curNum : nums){
            if(map.containsKey(curNum)) return true;
            else map.put(curNum, 1);
        }
        return false;
    }

思路二：min-max重映射

獲得該整數數組的最大值和最小值，并且利用最大值和最小值將原數組映射到新的數組。新的數組中數組的下標為原數組的值，如果遍歷過，則設置為1。

    public boolean containsDuplicate2(int[] nums){
        if(nums==null || nums.length<=1) return false;
        int length = nums.length;
        int min = nums[0];
        int max = nums[0];
        for(int curNum : nums){
            if(curNum < min) min = curNum;
            if(curNum > max) max = curNum;
        }
        //如果數組中最大值和最小值之間的數字個數小于數組長度，則一定存在重復值
        if(max - min + 1< length) return true;
        
        int[] result = new int[max-min+1];
        for(int curNum : nums){
            int newIndex = curNum - min;
            if(result[newIndex] != 0) return true;
            else result[newIndex]++;
        }
        return false;
    }

219 Contains DuplicateII

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 most k.

同I,還是整數數組，不同的是，要求兩個重復值的之間的間隔不得超過k

思路一：hashmap

還是通過hashmap存儲已經遍歷過的選項以及最近一次遍歷到時的下標值。如果重復數值的下標之間的值不超過k，那么就證明重復值滿足條件

    public boolean containsNearbyDuplicate(int[] nums, int k) {
        Map indexMap = new HashMap();
        for(int i = 0 ; i
思路二：set
保留一個含有最近k個值的集合，如果這個集合中存在和當前值相同的值，那么就存在相同的值，無需再去去判斷相同值之間的下標是否符合要求。
    public boolean containsNearbyDuplicate2(int[] nums, int k){
        Set potentialSet = new HashSet();
        for(int index = 0 ; index < nums.length ; index++){
            int curNum = nums[index];
            if(potentialSet.contains(curNum)){
                return true;
            }
            potentialSet.add(curNum);
            
            if(potentialSet.size() > k) potentialSet.remove(nums[index-k]);
        }
        return false;
    }
220 Contains DuplicateIII
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 the absolute difference between i and j is at most k.
這題在II的基礎上重新定義了相同的條件，也就是如果兩個值之間的絕對差不超過t，那么就可以稱這兩個值相同。
這里使用了treeset作為實現的數據結構，treeset通過堆的形式對集合中的數據進行存儲，從而我們可以通過某種順序獲得該集合中的所有順序。
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
            if(nums == null || nums.length <= 1 || k == 0) return false;
            
            TreeSet potentialNums = new TreeSet();
            for(int i = 0 ; i= curNum) return true;
                potentialNums.add(curNum);
                if(i >= k) potentialNums.remove((long)nums[i-k]);
            }
            return false;
    }

想要了解更多開發技術，面試教程以及互聯網公司內推，歡迎關注我的微信公眾號！將會不定期的發放福利哦~

GPU云服務器云服務器 Duplicates duplicated DUPLICATE Leetcod

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

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

[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
[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 PHP題解--D90 217. Contains Duplicate

摘要：題目鏈接題目分析返回給定的數組中是否有元素重復出現。思路用和即可最終代碼若覺得本文章對你有用，歡迎用愛發電資助。 D90 217. Contains Duplicate 題目鏈接 217. Contains Duplicate 題目分析返回給定的數組中是否有元素重復出現。思路用count和array_unique即可最終代碼

mingde 2019-07-01 14:01 評論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
[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