Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.
Follow up: Could you implement the O(n) solution?
Example 1:
Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.
Example 2:
Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9
Constraints:
0 <= nums.length <= 104
-109 <= nums[i] <= 109
/**
* Abstract: A close observation into the problem reveals the fact that every
* element belongs to one and only one sequence, which means we can somehow
* "invalidate the element after taking it into the longest consecutive
* sequence where it belongs" (by setting it to an impossible
* value, for example); this invalidation gives us a shorter array to traverse,
* whose elements are collected after every call to expand.
*
*/
void collect(int a[], int low, int n, int cn) { for (int i = low, j = 0; i < n; i++) { if (a[i] != INT_MIN) { a[j++] = a[i]; } } }
int expand(int a[], int n) {
int len = 0, tlen = 0, left = a[0] - 1, right = left + 2;
do {
tlen = 0;
for (int i = 0; i < n; i++) {
if (a[i] == left) {
a[i] = INT_MIN;
tlen += 1;
left -= 1;
} else if (a[i] == right) {
a[i] = INT_MIN;
tlen += 1;
right += 1;
}
}
len += tlen;
} while (tlen > 0);
return len;
}
int longestConsecutive(int* nums, int numsSize){
if (numsSize == 0) return 0;
int *a = nums, n = numsSize, len = 0, cn = n;
while (cn > 0) {
int tlen = expand(a, cn);
if (tlen > len) { len = tlen; }
int ncn = cn - tlen - 1;
collect(a, 1, cn, ncn);
cn = ncn;
}
return len + 1;
}
网友评论