共计 1540 个字符,预计需要花费 4 分钟才能阅读完成。
第一题 在排序数组中查找元素的第一个和最初一个地位
题目
谬误案例
func searchRange(nums []int, target int) []int {res:=make([]int,2)
n:=len(nums)
if n==1{if nums[0]==target{return res}else{res[0]=-1
res[1]=-1
return res
}
}
mid:=n/2
s1:=searchRange(nums[:mid],target)
s2:=searchRange(nums[mid:], target)
if s1[0]==-1&&s2[0]==-1{res[0]=-1
res[1]=-1
return res
}
if s1[0]==-1{res[0]=s2[0]+mid
res[1]=s2[1]+mid
}else if s2[0]==-1{res[0]=s1[0]
res[1]=s1[1]
}else{res[0]=s1[0]
res[1]=s2[1]+mid
}
return res
}
后果
….
起因是因为
正确解法
func searchRange(nums []int, target int) []int {leftmost := sort.SearchInts(nums, target)
if leftmost == len(nums) || nums[leftmost] != target {return []int{-1, -1}
}
rightmost := sort.SearchInts(nums, target + 1) - 1
return []int{leftmost, rightmost}
}
作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/solution/zai-pai-xu-shu-zu-zhong-cha-zhao-yuan-su-de-di-3-4/
起源:力扣(LeetCode)著作权归作者所有。商业转载请分割作者取得受权,非商业转载请注明出处。
解析
https://blog.csdn.net/luyuan4…
复杂度剖析
工夫复杂度:O(logn),其中 n 为数组的长度。二分查找的工夫复杂度为 O(logn),一共会执行两次,因而总工夫复杂度为 O(logn)。
空间复杂度:O(1)。只须要常数空间寄存若干变量。
第二题 合并区间
题目
解题思路
代码
func merge(intervals [][]int) [][]int {
// 先从小到大排序
sort.Slice(intervals,func(i,j int)bool{return intervals[i][0]<intervals[j][0]
})
// 再弄反复的
for i:=0;i<len(intervals)-1;i++{if intervals[i][1]>=intervals[i+1][0]{intervals[i][1]=max(intervals[i][1],intervals[i+1][1])// 赋值最大值
intervals=append(intervals[:i+1],intervals[i+2:]...)
i--
}
}
return intervals
}
func max(a,b int)int{
if a>b{return a}
return b
}
复杂度剖析
工夫复杂度:O(nlogn),其中 n 为区间的数量。除去排序的开销,咱们只须要一次线性扫描,所以次要的工夫开销是排序的 O(nlogn)。
空间复杂度:O(logn),其中 n 为区间的数量。这里计算的是存储答案之外,应用的额定空间。O(logn) 即为排序所须要的空间复杂度。
正文完