总公司网站备案后 分公司网站还需要备案吗,大流量ip网站怎么做,免费库存管理软件推荐,菏泽seo题目描述 题目#xff1a;给定一个未排序的整数数组 nums 找出数字连续的最长序列#xff0c;不要求序列 元素在原数组中连续 的长度 请你设计并实现时间复杂度为On的算法解决此问题 示例 1#xff1a; 输入#xff1a;nums [100,4,200,1,3,2] 输出#xff1a;4 解释给定一个未排序的整数数组 nums 找出数字连续的最长序列不要求序列 元素在原数组中连续 的长度 请你设计并实现时间复杂度为On的算法解决此问题 示例 1 输入nums [100,4,200,1,3,2] 输出4 解释最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4 。 关键 用哈希表来记录这个字符是否出现过 然后遍历数组 对于每个数字 检查它是否是某个序列的开始,并更新最大长度 做不出来可以先看看题目实在没思路再往下看看思路 解题思路 可以用一个哈希表存储需要查找的字符串判断当前数字是否在哈希表中 如果当前数字在哈希表中那么它可能是一个连续的序列的起点找到这个起点向后遍历确定最大长度返回 解题步骤 判断边界条件创建哈希表存储这个数将每个数字添加到哈希表中初始化序列最长的长度、和当前查找的序列长度遍历这个哈希表中的所有数字找到它的最长序列返回 代码实现
func longestConsecutive(nums []int) int {// 1. 左边界判断 做算法 的第一步if len(nums) 0 {return 0}// 2.初始化哈希表set : make(map[int]bool)// 3.将数据存储到哈希表中for num : range nums {set[num] true}// 3. 初始化 最长序列maxLength : 0for num : range set {// 如果当前数字的前一个字符不在哈希表中 那么当前这个数字就有可能是这个序列的起点if !set[num-1] {currentNum : numcurrentSteark : 1}for set[currentNum1] {currentNumcurrentSteark}// 4.找到最大的那个序列长度maxLength : max(maxLength,currentSteark)}}// 5.返回最大值的序列长度return maxLength
}代码测试
func main() {nums : []int{100, 4, 200, 1, 3, 2}fmt.Println(Longest consecutive sequence length is:, longestConsecutive(nums))
}测试结果 QA
为什么使用哈希表来完成这个算法 1 .使用哈希表 可以最快效率的查到该元素 哈希表的复杂度为0(1) 2. 满足这个题目的时间复杂度On的要求 if !set[num-1] 做了什么事 这里说明了 如果当前元素的前一个元素不存在这个哈希表中的话那么这个元素就可能是这个序列的起点。那么接下来的代码就会从这个数字开始找这个序列。
