ContainsDuplicateOPT [source code]

public class ContainsDuplicateOPT {
    public boolean containsDuplicate(int[] nums) {
        if (nums.length == 0 || nums.length == 1) return false;
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for (int num : nums) {
            if (num < min) min = num;
            if (num > max) max = num;
        }
        boolean[] index = new boolean[max - min + 1];
        for (int num : nums) {
            if (index[num - min]) return true;
            else index[num - min] = true;
        }
        return false;
    }
}

这个是 submission 最优解, 4ms, 99%;

这个算法其实一开始我自己也想到了, 其实就是用array 来实现 hash (value as index), 而不是借助于 table. 当时没有继续做下去是因为题目没有给 domain, 不过这个其实很幼稚, 这里这个人这种做法其实前面见过的, 一个 array 给你, 你永远是知道 domain 的, 只要自己过一下最大最小值就行了(当然worst case的话是没有办法保证的, 这里讨论的是practical case); 除开这个技巧, 这个算法本身并没有什么其他的地方;

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