电脑网站你懂我意思正能量,公司名称大全及寓意,网站抄袭我网站,wordpress清理主题原题#xff1a;128. 最长连续序列 题解#xff1a;
官方题解#xff1a;. - 力扣#xff08;LeetCode#xff09;题解#xff0c;最长连续序列 #xff1a;哈希表
官方解题思路是先去重#xff0c;然后判断模板长度的数值是否存在#xff0c;存在就刷新#xff0c…原题128. 最长连续序列 题解
官方题解. - 力扣LeetCode题解最长连续序列 哈希表
官方解题思路是先去重然后判断模板长度的数值是否存在存在就刷新最终找到最大值。
这里我自己研究了下实际也是暴力解法。纯暴力解法会超时这里利用了二分法查找的理念
首先去重然后排序固定begin然后找最大的end返回使用二分法理念进行查找依次遍历在已经找到的最大值返回
自己尝试了下部分通过有些边界值不太好控制而且输入里面有负数也不太好计算。 还有一种解题方法就是在官方题解上做个变化
首先去重然后排序依次遍历找到满足的最长子数组返回其长度。 代码
func longestConsecutive(nums []int) int {// 如果数组为空或者只有一个元素直接返回数组长度if len(nums) 1 {return len(nums)}// 去重numSet : map[int]bool{}for _, num : range nums {numSet[num] true}// 排序numTemp : make([]int, 0)for num : range numSet {numTemp append(numTemp, num)}sort.Ints(numTemp)// fmt.Printf(numTemp %v\n, numTemp)// 暴力解法longestStreak : 0for begin : range numTemp {// 当剩余的个数小于当前最大长度则后面不可能有满足条件的更大的值返回if beginlongestStreak len(numTemp) {return longestStreak 1}temp : BinarySearchMatch(numTemp, begin, longestStreak)if longestStreak temp {longestStreak temp}}return longestStreak 1
}func BinarySearchMatch(numTemp []int, begin, cur int) int {longestStreak : cur// 当前最大可用差值curMaxDiff : len(numTemp) - begin - 1// 使用二分法的理念查询满足条件的数据for end : len(numTemp) - 1; end begin; {// fmt.Printf(begin %v, end %v, curMaxDiff %v\n, begin, end, curMaxDiff)// 索引差值超过最大值返回end超过数组范围返回if curMaxDiff len(numTemp) || end len(numTemp) {break}// 差值为0时有可能会遗漏一个判断end的下一个是否满足条件if curMaxDiff 0 {if end len(numTemp)-1 numTemp[end1]-numTemp[begin] end1-begin {longestStreak end 1 - begin}if end begin numTemp[end-1]-numTemp[begin] end-1-begin {longestStreak end - 1 - begin}if end begin numTemp[end]-numTemp[begin] end-begin {longestStreak end - begin}break}// 数值差值valDiff : numTemp[end] - numTemp[begin]// 索引差值indexDiff : end - begin// 二分法找到合适的索引end// 索引差值 数值差值数值太大了中间有不连续的往前移动curMaxDiff/2if valDiff indexDiff indexDiff ! 0 {curMaxDiff curMaxDiff / 2end end - curMaxDiffcontinue}// 索引差值 数值差值这种不可能存在因为已经去重了// 索引差值 数值差值后面可能还有满足条件的继续找if valDiff indexDiff {// 刷新最大值if longestStreak valDiff {break}longestStreak valDiff// end后移curMaxDiff/2curMaxDiff curMaxDiff / 2end end curMaxDiffcontinue}}return longestStreak
}
第二种方法
func longestConsecutive(nums []int) int {// 如果数组为空或者只有一个元素直接返回数组长度if len(nums) 1 {return len(nums)}// 去重numSet : map[int]bool{}for _, num : range nums {numSet[num] true}// 排序numTemp : make([]int, 0)for num : range numSet {numTemp append(numTemp, num)}sort.Ints(numTemp)//fmt.Printf(numTemp %v\n, numTemp)// 暴力解法longestStreak : 0for num : range numTemp {if num len(numTemp)-1 numTemp[num]1 numTemp[num1] {currentNum : numcurrentStreak : 1for currentNum len(numTemp)-1 numTemp[currentNum]1 numTemp[currentNum1] {currentNumcurrentStreak}if longestStreak currentStreak {longestStreak currentStreak}}}return longestStreak
}
