leetcode 217 Contains Duplicate

philadelphia 發(fā)布于2019-08-15 13:53 / 1916人閱讀

摘要：題目詳情輸入一個(gè)整數(shù)的數(shù)組，如果數(shù)組中的元素有重復(fù)的，那么返回，如果數(shù)組中的元素都是唯一的，那么返回思路這道題理解起來比較簡單，首先還是要注意一下邊界條件異常輸入，對(duì)于長度小于等于的數(shù)組做一個(gè)直接的返回對(duì)于這種要考慮數(shù)組中元素的重復(fù)的問題，

題目詳情

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ù)的，那么返回true，如果數(shù)組中的元素都是唯一的，那么返回false

思路

這道題理解起來比較簡單，首先還是要注意一下邊界條件／異常輸入，對(duì)于長度小于等于1的數(shù)組做一個(gè)直接的返回

對(duì)于這種要考慮數(shù)組中元素的重復(fù)的問題，就很容易想到hashmap，key就是元素的值，value可以表示元素的個(gè)數(shù)，對(duì)于已經(jīng)存在的key，直接返回true,但是這種解法需要額外O(n)的空間

在使用hashmap求解的過程中，我意識(shí)到了這個(gè)方法還是想的復(fù)雜了，數(shù)組元素的重復(fù)性問題通常還有一種思路就是數(shù)組的預(yù)排序

先對(duì)輸入數(shù)組進(jìn)行預(yù)排序，然后只需要比較數(shù)組和它相臨的元素是否相等就可以了

解法一 HashMap

    public boolean containsDuplicate(int[] nums) {
        int length = nums.length;
        if(length <= 1){
            return false;
        }     
        HashMap count = new HashMap();
        count.put(nums[0], 1);
        
        for(int i = 1;i
解法二 預(yù)排序算法
    public boolean containsDuplicate(int[] nums) {
        int length = nums.length;
        if(length <= 1){
            return false;
        } 
        Arrays.sort(nums);
        for(int i=0 ;i