題目描述

給定一個未排序的整數數組 nums ，找出數字連續的最長序列（不要求序列元素在原數組中連續）的長度。

請你設計并實現時間復雜度為 O(n) 的算法解決此問題。

示例 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 <= 10^5

-10^9 <= nums[i] <= 10^9

題解

思路

先排序再比較計數；
如果相鄰兩數差一計數，如果相等進入下一層循環判斷；
如果后面數與前一個數既不相等又不比前一個多一，重值計數為1.

代碼

int cmp(const void* a, const void* b)
{// Custom comparison function for qsort to sort integers in ascending orderreturn (long long)*(int*)a - (long long)*(int*)b;
}int longestConsecutive(int* a, int n)
{// Check for edge casesif (a == NULL || n == 0) {return 0;}/* The  qsort  function in C is used to sort an array in ascending order. * It takes the following parameters: * base: Pointer to the array to be sorted. * nmemb: Number of elements in the array. * size: Size in bytes of each element in the array. * compar: Pointer to a comparison function that determines the order of elements. * The comparison function ( compar ) should return an integer less than, * equal to, or greater than zero if the first argument is considered to be * respectively less than, equal to, or greater than the second argument. * void qsort(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *));*/// Sort the input array 'a' in ascending orderqsort(a, n, sizeof(int), cmp);int t = a[0]; // Initialize 't' with the first element of the sorted arrayint cnt = 1; // Initialize 'cnt' to keep track of the current consecutive sequence lengthint max = 1; // Initialize 'max' to keep track of the maximum consecutive sequence length// Iterate through the sorted array to find the longest consecutive sequencefor (int i = 1; i < n; i++) {if (a[i] == t) {// If the current element is equal to the previous element, skip itcontinue;} else if ((long long)a[i] - t == 1LL) {// If the current element is consecutive to the previous elementt = a[i]; // Update 't' to the current elementcnt++; // Increment the consecutive countif (max < cnt) {max = cnt; // Update 'max' if a longer consecutive sequence is found}} else {// If the current element is not consecutive to the previous elementt = a[i]; // Update 't' to the current elementcnt = 1; // Reset the consecutive count}}return max; // Return the maximum consecutive sequence length
}