leetcode217.219.220 contains duplicate

tulayang 發(fā)布于2019-08-16 10:56 / 1714人閱讀

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

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.

輸入一個(gè)整數(shù)數(shù)組，查看數(shù)組中是否存在重復(fù)的值。

思路一：hashmap or hashset

使用java中的數(shù)據(jù)結(jié)構(gòu)將已經(jīng)遍歷起來的值存儲(chǔ)起來，然后查詢當(dāng)前的值是否已經(jīng)便利過

    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重映射

獲得該整數(shù)數(shù)組的最大值和最小值，并且利用最大值和最小值將原數(shù)組映射到新的數(shù)組。新的數(shù)組中數(shù)組的下標(biāo)為原數(shù)組的值，如果遍歷過，則設(shè)置為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;
        }
        //如果數(shù)組中最大值和最小值之間的數(shù)字個(gè)數(shù)小于數(shù)組長度，則一定存在重復(fù)值
        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,還是整數(shù)數(shù)組，不同的是，要求兩個(gè)重復(fù)值的之間的間隔不得超過k

思路一：hashmap

還是通過hashmap存儲(chǔ)已經(jīng)遍歷過的選項(xiàng)以及最近一次遍歷到時(shí)的下標(biāo)值。如果重復(fù)數(shù)值的下標(biāo)之間的值不超過k，那么就證明重復(fù)值滿足條件

    public boolean containsNearbyDuplicate(int[] nums, int k) {
        Map indexMap = new HashMap();
        for(int i = 0 ; i
思路二：set
保留一個(gè)含有最近k個(gè)值的集合，如果這個(gè)集合中存在和當(dāng)前值相同的值，那么就存在相同的值，無需再去去判斷相同值之間的下標(biāo)是否符合要求。
    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的基礎(chǔ)上重新定義了相同的條件，也就是如果兩個(gè)值之間的絕對(duì)差不超過t，那么就可以稱這兩個(gè)值相同。
這里使用了treeset作為實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)，treeset通過堆的形式對(duì)集合中的數(shù)據(jù)進(jìn)行存儲(chǔ)，從而我們可以通過某種順序獲得該集合中的所有順序。
    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;
    }

想要了解更多開發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號(hào)！將會(huì)不定期的發(fā)放福利哦~