算法刷题：一步步优化系列01.最长连续序列

题目链接：

• 最长连续序列

• 暴力解法 (超时)
• 优化内层查找 (On - > O1 但超时)
  • 问题：重复的边界会重新迭代
• 优化重复迭代：在值域而非定义域迭代，去重 (超时)
  • 问题：值域大且元素离散度大时，会大量迭代到不存在的元素，空迭代
• 优化空迭代：HashSet去重，每次迭代的元素都存在 (26ms)
• 从左边界重复入手再优化：HashMap存右界解法 (27ms)
• 另解：排序+链式判断（26ms）

暴力解法 (超时)

class Solution {
    public int longestConsecutive(int[] nums) {
        int n = nums.length;
        int ans = 0;
        // 遍历数组中的每个元素num
        for (int i = 0; i < n; i++) {
            // 以num为起点，每次+1向后遍历num+1,num+2,num+3...
            int cur = nums[i] + 1;
            while (true) {
                // 标识是否在数组中找到了cur
                boolean flag = false;
                // 在数组中找cur
                for (int j = 0; j < n; j++) {
                    if (nums[j] == cur) {
                        flag = true;
                        break;
                    }
                }
                if (!flag) {
                    break;
                }
                cur ++;
            }
            ans = Math.max(ans, cur - nums[i]);
        }
        return ans;
    }
}

优化内层查找 (On - > O1 但超时)

class Solution {
    Map<Integer, Integer> map;
    public int longestConsecutive(int[] nums) {
        map = new HashMap<>();
        for(int i = 0; i < nums.length; i++){
            map.putIfAbsent(nums[i], 1);
        }

        int n = nums.length;
        int ans = 0;
        // 遍历数组中的每个元素num
        for (int i = 0; i < n; i++) {
            // 以num为起点，每次+1向后遍历num+1,num+2,num+3...
            int cur = nums[i] + 1;
            while (map.containsKey(cur)) {
                cur ++;
            }
            ans = Math.max(ans, cur - nums[i]);
        }
        return ans;
    }
    
}

问题：重复的边界会重新迭代

优化重复迭代：在值域而非定义域迭代，去重 (超时)

class Solution {
    public int longestConsecutive(int[] nums) {
        int min = 0x3f3f3f3f, max = -0x3f3f3f3f;
        Map<Integer, Integer> map = new HashMap<>(); 
        for(int i = 0; i < nums.length; i++){
            map.putIfAbsent(nums[i], 1);
            if(min > nums[i]) min = nums[i];
            if(max < nums[i]) max = nums[i];
        }
        int ans = 0;
        for (int i = min; i <= max; i++) { 
            int cur = i;
            while (map.containsKey(cur)) {
                cur ++;
            }
            ans = Math.max(ans, cur - i);//nums[i]);
            i = cur;
        }
        return ans;
    }
}

问题：值域大且元素离散度大时，会大量迭代到不存在的元素，空迭代

优化空迭代：HashSet去重，每次迭代的元素都存在 (26ms)

class Solution {
    public int longestConsecutive(int[] nums) {
        int ans = 0, n = nums.length;
        Set<Integer> set = new HashSet<>(128);
        for(int i = 0; i < n; i++) set.add(nums[i]);
        for(Integer k : set) {
            int cur = k;
            if(set.contains(k - 1)) continue;
            while (set.contains(cur)) {
                cur ++;
            } ans = Math.max(ans, cur - k);
        } return ans;
    }
}

从左边界重复入手再优化：HashMap存右界解法 (27ms)

class Solution {
    public int longestConsecutive(int[] nums) {
        int ans = 0, n = nums.length;
        Map<Integer, Integer> map = new HashMap<>(128);
        for(int i = 0; i < n; i++) 
            map.putIfAbsent(nums[i], nums[i]);

        for(int num : nums) {
            if(map.containsKey(num - 1)) continue;
            int rgt = map.get(num);
            if(rgt != num) continue;

            while(map.containsKey(rgt)){
                rgt++;
            } map.put(num, rgt);
            ans = Math.max(ans, rgt - num); 
            
        } return ans;
    }
}

另解：排序+链式判断（26ms）

class Solution {
    public int longestConsecutive(int[] nums) {
        if(nums.length == 0) return 0;

        int ans = 0, cur = 0;
        // Arrays.sort(nums);
        sort(nums);
        for(int i = 1; i < nums.length; i++){
            // System.out.println(nums[i] - nums[i - 1]);
            int dif = nums[i] - nums[i - 1];
            if(dif == 0) continue;
            else if(dif == 1) ++cur;
            else {
                ans = Math.max(ans, cur + 1);
                cur = 0;
            }
        }
        ans = Math.max(ans, cur + 1);
        return ans;
    }
    
    void sort(int [] nums){
        int [] tmp = new int[nums.length];
        dfs(nums, tmp, 0, nums.length - 1);
    }
    void dfs(int [] nums, int [] tmp, int lft, int rgt){
        if(lft >= rgt) return;
        int mid = (lft + rgt) >> 1;
        dfs(nums, tmp, lft, mid);
        dfs(nums, tmp, mid + 1, rgt);
        int i = lft, j = mid + 1, p = 0;
        while(i <= mid && j <= rgt)
            tmp[p++] = nums[i] < nums[j] ? nums[i++] : nums[j++];
        while(i <= mid) tmp[p++] = nums[i++];
        while(j <= rgt) tmp[p++] = nums[j++];
        for(int u = 0; u < p; u++){
            nums[u + lft] = tmp[u];
        }
    }
}