給定一個(gè)未排序的整數(shù)數(shù)組 nums 涩拙，找出數(shù)字連續(xù)的最長序列（不要求序列元素在原數(shù)組中連續(xù)）的長度

進(jìn)階：你可以設(shè)計(jì)并實(shí)現(xiàn)時(shí)間復(fù)雜度為 O(n) 的解決方案嗎际长？

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

示例1：

輸入：nums = [100,4,200,1,3,2]
輸出：4
解釋：最長數(shù)字連續(xù)序列是 [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解法

思路：

• 最簡單直接的方法：先排序也颤，再記錄連續(xù)值，能計(jì)算但效率不高

• 官方解利用hashset來進(jìn)行查找郁轻，這里有個(gè)模糊點(diǎn)翅娶，hashset的contains方法的時(shí)間復(fù)雜度的問題，這里是波動(dòng)的好唯，通過HashSet源碼可以發(fā)現(xiàn)hashset內(nèi)部持有了一個(gè)特殊的HashMap（value為Object PRESENT = new Object()）他的contains方法即為hashmap的方法竭沫，在這里，也有遍歷骑篙，所有不能完全定義為O（1）蜕提，這與hashset的table長度有關(guān)，但經(jīng)過table數(shù)組的處理是必定小于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];//以左側(cè)為基準(zhǔn)值
        while (start < end) {//為雙指針靶端， 重合時(shí)跳出
            // 從右向左尋找谎势，一直找到比參照值還小的數(shù)值，進(jìn)行替換
            while (start < end && args[end] >= pivot) {
                end--;//找到比基準(zhǔn)值小的數(shù)值的位置
            }
            if (start < end) {
                //因?yàn)榛鶞?zhǔn)值已被記錄杨名，所以直接更新即可脏榆，args[end]會(huì)在下一次更新
                args[start] = args[end];
            }
            // 從左向右尋找，一直找到比參照值還大的數(shù)組台谍，進(jìn)行替換
            while (start < end && args[start] < pivot) {
                start++;
            }
            if (start < end) {
                args[end] = args[start];
            }
        }
        args[start] = pivot;//此時(shí) 雙指針都指向了應(yīng)該在的位置须喂，更新該值即可
        return start;
    }
}

image

官方解

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

1. 哈希表

   利用hashset去重這一步很機(jī)智，我就忽略了

   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

   • 時(shí)間復(fù)雜度：O(n),時(shí)間復(fù)雜度因?yàn)槲窗琧ontains的考慮，所以這里個(gè)人覺得不能認(rèn)定為O(n)

   • 空間復(fù)雜度：O(n)