网站源码如何使用,怎样在微信上开发小程序,太原建南站,商标注册查询官网网站给定一个未排序的整数数组 nums #xff0c;找出数字连续的最长序列#xff08;不要求序列元素在原数组中连续#xff09;的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
#include iostream
#include vector
#include unordered_set找出数字连续的最长序列不要求序列元素在原数组中连续的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
#include iostream
#include vector
#include unordered_setint longestConsecutiveSequence(const std::vectorint nums) {std::unordered_setint numSet(nums.begin(), nums.end());int maxLength 0;for (int num : numSet) {// 只考虑当前数字作为序列起点的情况if (numSet.find(num - 1) numSet.end()) {int currentNum num;int currentLength 1;while (numSet.find(currentNum 1) ! numSet.end()) {currentNum;currentLength;}maxLength std::max(maxLength, currentLength);}}return maxLength;
}int main() {std::vectorint nums {100, 4, 200, 1, 3, 2};int result longestConsecutiveSequence(nums);std::cout The length of the longest consecutive sequence is: result std::endl;return 0;
}
这段代码首先将输入的整数数组构建为一个 unordered_set以便快速查找数字是否存在。然后遍历数组中的每个数字对于每个数字判断是否存在比它小的数字即作为某个序列的起点如果不存在则从该数字开始向后搜索连续的数字计算当前连续序列的长度。最后更新最长连续序列的长度并返回。
整个算法的时间复杂度为 O(n)其中 n 为输入数组的长度因为使用了哈希集合来存储数字判断数字是否存在的时间复杂度为 O(1)。
不考虑时间复杂度纯从解题角度还有一种解决方案
int longestConsecutive(vectorint nums) {int len nums.size();if (len 0) {return 0;}int maxlen 1;int maxt 1;vectorint numst nums;unordered_mapint, int m;sort(numst.begin(), numst.end());for (int i 0; i len; i) {if (m.find(nums[i]) m.end()) {m.insert(make_pair(nums[i], 1));}else {m[nums[i]] m[nums[i]] 1;}}for (int i 0; i len-1; i) {if ((m.find(numst[i] 1) ! m.end())) {if (m[numst[i] 1]) {maxt;m[numst[i] 1] 0;}}else {maxt 1;}maxlen max(maxlen, maxt);}return maxlen;}
};时间复杂度为 O(n log n)空间复杂度为 O(n)。
时间复杂度分析
对输入数组 nums 进行排序的时间复杂度为 O(n log n)。 第一个 for 循环遍历整个数组并将元素及其出现次数存储在 unordered_map 中时间复杂度为 O(n)。 第二个 for 循环遍历排序后的数组对于每个元素查找其是否存在相邻的元素并更新最长连续序列的长度时间复杂度为 O(n)。 综合以上步骤总体时间复杂度为 O(n log n) O(n) O(n) O(n log n)。
空间复杂度分析
额外使用了一个大小为 n 的 vector numst 来存储 nums 的副本空间复杂度为 O(n)。 使用了一个 unordered_mapint, int m 来存储元素及其出现次数空间复杂度也为 O(n)。 综合以上两部分总体空间复杂度为 O(n)。
这个方案使用了排序和哈希表的方法来计算最长连续序列的长度。和上一个方案相比的优势和劣势
优势
排序后查找相邻元素更方便 通过对数组进行排序可以更容易地找到相邻的元素从而判断是否存在连续序列。
使用哈希表存储元素及其出现次数 哈希表在查找、插入操作上具有 O(1) 的时间复杂度能够有效地存储元素及其出现次数方便后续的查找和更新操作。
劣势
时间复杂度较高 使用排序的方法将时间复杂度提升到了 O(n log n)而哈希表的插入和查找操作虽然是 O(1)但仍需遍历整个数组总体时间复杂度仍为 O(n log n)。
空间复杂度较高 使用了额外的哈希表来存储元素及其出现次数增加了空间复杂度。
逻辑复杂度高 需要维护排序后的数组以及哈希表增加了代码的复杂度和维护成本。
相比之下前一种方案代码逻辑清晰且时间复杂度为 O(n)空间复杂度也较低不需要额外的排序和哈希表操作。
