第一题 在排序数组中查找元素的第一个和最初一个地位
题目
谬误案例
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) 即为排序所须要的空间复杂度。