【LeetCode】Contains Duplicate解題報告

Contains Duplicate
[LeetCode]
https://leetcode.com/problems/contains-duplicate/
Total Accepted: 86528 Total Submissions: 209877 Difficulty: Easy
Question
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. 重複要素があるかどうかを判断する
Ways
この問題は三つの解法を思いついた.
方法1,2つのforサイクルソートは,肯定的に効率が低い.
方法2では,ArrayListを用いて,既に追加した要素に挿入するか否かを判断する.事実はこの方法がタイムアウトしたことを証明した.
方法3は,HashMapを用い,後にHashSetを用いた.
HashMapの使用:

public class Solution {
    public boolean containsDuplicate(int[] nums) {
        HashMap map = new HashMap();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i])) {
                return true;
            } else {
                map.put(nums[i], nums[i]);
            }
        }
        return false;
    }
}

AC:17ms
HashSetの使用:

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

AC:16ms
資料を調べると、ここではHashSetを使うべきです.HashMapはキー値ペアを格納しているので、無限で重複しない配列で判断すれば、複雑さと時間の消費が多いからです.一方,HashSetの利点は,集合中に重複する値が許されないHashSetインタフェースを実現し,記憶を行う際にはまず判断を行い,contain法を用いることで複雑度と時間消費が減少することである.
ええと、もっと簡単な方法があると思いますか.OJが私の効率が悪いことを示しているのを見たからです.しかし、見つからなかった.
Date
2016/5/1 10:55:17