ContainsDuplicate [source code]

public class ContainsDuplicate {
    public boolean containsDuplicate(int[] nums) {
        Map<Integer, Boolean> map = new HashMap<>();
        for (int i : nums) {
            if (map.get(i) != null) return true;
            map.put(i, true);
        }
        return false;
    }
}

这个问题总体很简单了, 速度是21ms, 38%, 不算好, 估计有更聪明的算法;

editorial里面提到的一个很好的办法就是先 sort, 然后比较adjacent 就行了:

public boolean containsDuplicate(int[] nums) {  
    Arrays.sort(nums);  
    for (int i = 0; i < nums.length - 1; ++i) {  
        if (nums[i] == nums[i + 1]) return true;  
    }  
    return false;  
}

最后的速度是6ms, 91%. 可见HashTable 这种东西看起来好像是 constant, 实际用起来速度比用纯粹的primitive structure要慢很多;

另外就算是用 table, 也应该学会使用set.contains(x)这个 API;

Problem Description

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.

Difficulty:Easy
Category:Algorithms
Acceptance:45.29%
Contributor: LeetCode
Companies
palantir airbnb yahoo
Related Topics
array hash table
Similar Questions
Contains Duplicate II Contains Duplicate III