Day66 最长连续序列

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度

进阶：你可以设计并实现时间复杂度为 O(n) 的解决方案吗？

https://leetcode-cn.com/problems/longest-consecutive-sequence/

示例1：

输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

示例2：

输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9

提示：

0 <= nums.length <= 104
-109 <= nums[i] <= 109

Java解法

思路：

• 最简单直接的方法：先排序，再记录连续值，能计算但效率不高

• 官方解利用hashset来进行查找，这里有个模糊点，hashset的contains方法的时间复杂度的问题，这里是波动的，通过HashSet源码可以发现hashset内部持有了一个特殊的HashMap（value为Object PRESENT = new Object()）他的contains方法即为hashmap的方法，在这里，也有遍历，所有不能完全定义为O（1），这与hashset的table长度有关，但经过table数组的处理是必定小于O（n）的
  

  image

package sj.shimmer.algorithm.m4_2021;

/**
 * Created by SJ on 2021/4/3.
 */

class D66 {
    public static void main(String[] args) {
        System.out.println(longestConsecutive(new int[]{100,4,200,1,3,2}));
        System.out.println(longestConsecutive(new int[]{0,3,7,2,5,8,4,6,0,1}));
        System.out.println(longestConsecutive(new int[]{1,2,0,1}));
    }
    public static int longestConsecutive(int[] nums) {
        int result = 0;
        if (nums != null) {
            int[] swap = quickSwap(nums, 0, nums.length-1);
            int temp = 0;
            for (int i = 0; i < swap.length; i++) {
                temp++;
                if (i+1<swap.length) {
                    if (swap[i+1] == swap[i]){
                        temp--;
                    }else if (swap[i+1] != swap[i]+1){
                        result = Math.max(result,temp);
                        temp = 0;
                    }
                }
            }
            result = Math.max(result,temp);
        }
        return result;
    }
    public static int[] quickSwap(int[] nums, int startIndex, int endIndex) {
        if (startIndex < endIndex) {
            int mid = findPosition(nums, startIndex, endIndex);
            quickSwap(nums, startIndex, mid - 1);
            quickSwap(nums, mid + 1, endIndex);
        }
        return nums;
    }
    public static int findPosition(int[] args, int start, int end) {
        int pivot = args[start];//以左侧为基准值
        while (start < end) {//为双指针， 重合时跳出
            // 从右向左寻找，一直找到比参照值还小的数值，进行替换
            while (start < end && args[end] >= pivot) {
                end--;//找到比基准值小的数值的位置
            }
            if (start < end) {
                //因为基准值已被记录，所以直接更新即可，args[end]会在下一次更新
                args[start] = args[end];
            }
            // 从左向右寻找，一直找到比参照值还大的数组，进行替换
            while (start < end && args[start] < pivot) {
                start++;
            }
            if (start < end) {
                args[end] = args[start];
            }
        }
        args[start] = pivot;//此时 双指针都指向了应该在的位置，更新该值即可
        return start;
    }
}

image

官方解

https://leetcode-cn.com/problems/longest-consecutive-sequence/solution/zui-chang-lian-xu-xu-lie-by-leetcode-solution/

1. 哈希表

   利用hashset去重这一步很机智，我就忽略了

   class Solution {
      public  int longestConsecutive(int[] nums) {
           int result = 0;
                Set<Integer> num_set = new HashSet<Integer>();
           for (int num : nums) {
               num_set.add(num);
           }
   
           int longestStreak = 0;
   
           for (int num : num_set) {
               if (!num_set.contains(num - 1)) {
                   int currentNum = num;
                   int currentStreak = 1;
   
                   while (num_set.contains(currentNum + 1)) {
                       currentNum += 1;
                       currentStreak += 1;
                   }
   
                   longestStreak = Math.max(longestStreak, currentStreak);
               }
           }
   
           return longestStreak;
       }
   

   image

   • 时间复杂度：O(n),时间复杂度因为未包含contains的考虑，所以这里个人觉得不能认定为O(n)

   • 空间复杂度：O(n)