网站怎么挣钱,昭通市网站建设,网站建设销售人才简历,c 网站开发架构题目描述
给定一个未排序的整数数组 nums #xff0c;找出数字连续的最长序列#xff08;不要求序列元素在原数组中连续#xff09;的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1#xff1a;
输入#xff1a;nums [100,4,200,1,3,2]
输出找出数字连续的最长序列不要求序列元素在原数组中连续的长度。
请你设计并实现时间复杂度为 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 105-109 nums[i] 109
思考
第一反应对nums进行排序然后查找最大序列。
但是时间复杂度为 O ( n l o g n ) \Omicron (nlogn) O(nlogn)
然后想一下可以枚举每个数字比如x。然后查看x1,x2,x3是否出现过。
朴素的话时间复杂度为 O ( n 2 ) \Omicron (n^2) O(n2)
通过剪枝如果处理x, 存在x-1的话肯定不用进行这次遍历(因为结果肯定会小于从x-1开始)。时间复杂度 O ( n ) \Omicron (n) O(n)
然后还可以使用并查集。比如2,3,4在同一个集合。7,8,9,10在一个集合。但是需要维护集合大小。
代码实现
感觉第三种实现比较有意思。虽然实际上写起来就感觉运行会很慢。权当复习并查集了
//
// Created by Anti on 2023/9/1.
//
#include gtest/gtest.h
#include logger.h/*** description 给定一个未排序的整数数组 nums 找出数字连续的最长序列不要求序列元素在原数组中连续的长度。* 请你设计并实现时间复杂度为 O(n) 的算法解决此问题。*/
class Solution {
private:std::unordered_mapint,int father_;std::unordered_mapint,size_t size_; // 所在并查集的大小int max_size_{}; // 最大的并查集大小/*** 返回x的祖先。约定祖先较小。* param x* return*/auto get_root(int x) - int {if(father_[x]x) {return x;}return father_[x] get_root(father_[x]);}
public:int longestConsecutive(std::vectorint nums) {max_size_ !nums.empty();for(const auto num:nums) {father_[num] num;size_[num] 1;}for(const auto num:nums) {auto y num1;if(father_.count(num1)) {auto father_x get_root(num);auto father_y get_root(y); // 1 3 5 4if(father_x!father_y) {if(father_x father_y) {std::swap(father_x, father_y);}father_[father_y] father_x;size_[father_x] size_[father_y];max_size_ std::max(max_size_, int(size_[father_x]));}}}return max_size_;}
};TEST(S128,SAMPLE1) {Solution s;std::vectorint nums {100,4,200,1,3,2};EXPECT_EQ(s.longestConsecutive(nums),4);
}TEST(S128,SAMPLE2) {Solution s;std::vectorint nums {0,3,7,2,5,8,4,6,0,1};EXPECT_EQ(s.longestConsecutive(nums),9);
}TEST(S128,TRICK1) {Solution s;std::vectorint nums {0};EXPECT_EQ(s.longestConsecutive(nums),1);
}
TEST(S128,TRICK2) {Solution s;std::vectorint nums {};EXPECT_EQ(s.longestConsecutive(nums),0);
}
