How to solve this situation when input nums pervade with hash collision?


  • 0
    A

    I accept the problem with the code as follows, but i don't think the complexity is O(n), because the hash collision in the hashset may descend the set.contains(num[i]) operation take O(n) time.

    Does the description of problem have something wrong?

    public int longestConsecutive(int[] num) {
        int len = num.length;
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < num.length; i++) {
            set.add(num[i]);
        }
        int max = 0;
        for (int i = 0; i < num.length; i++) {
            if (set.contains(num[i])) {
                int count = 1;
                int left = num[i] - 1;
                while (set.contains(left)) {
                    count++;
                    set.remove(left);
                    left--;
                }
                int right = num[i] + 1;
                while (set.contains(right)) {
                    count++;
                    set.remove(right);
                    right++;
                }
                if (count > max) {
                    max = count;
                }
            }
        }
        return max;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.