why the O(nlogn) solution with sort is faster than O(n) solution with union set????


  • 0
    T
     // union set solution beat 78%
        public int longestConsecutive(int[] nums) {
            Set<Integer> set = new HashSet<>();
            for (int l : nums) {
                set.add(l);
            }
            int max = 0;
            Set<Integer> tm= new HashSet<>();
            for (int k : set) {
                if (!set.contains(k - 1) && !tm.contains(k)) {
                    int y = k + 1;
                    while (set.contains(y)) {
                        y += 1;
                        tm.add(y);
                    }
                    max = Math.max(max, y - k);
                }
            }
            return max;
        }
    
    // sort solution beat 97%
    public int longestConsecutive(int[] nums) {
            if (nums.length == 0) {
                return 0;
            }
            Arrays.sort(nums);
            int max = 1;
            int tmp = 1;
            for (int i = 1; i < nums.length; i ++) {
                if (nums[i] - nums[i - 1] == 1) {
                    tmp ++;
                }else if(nums[i] == nums[i - 1]) {
                    continue;
                }else{
                    max = Math.max(tmp, max);
                    tmp = 1;
                }
            }
            return Math.max(tmp, max);
        }
    

Log in to reply
 

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