[golang] leetcode intermediate - find the first and last position of an element in a sorted array & Merge interval

The first question is Find the first and last positions of the elements in the sort array

subject

Wrong cases

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
}

result

....

The reason is because

The correct solution

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}
}

 author ：LeetCode-Solution
 link ：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/
 source ： Power button （LeetCode）
 The copyright belongs to the author . Commercial reprint please contact the author for authorization , Non-commercial reprint please indicate the source .

analysis

https://blog.csdn.net/luyuan4...

Complexity analysis

Time complexity ：O(logn) , among n Is the length of the array . The time complexity of binary search is O(logn), It will be executed twice , So the total time complexity is O(logn).

Spatial complexity ：O(1) . You just need constant space to hold a few variables .

The second question is Merge range

subject

Their thinking

Code

func merge(intervals [][]int) [][]int {
    // Sort from small to large 
    sort.Slice(intervals,func(i,j int)bool{
        return intervals[i][0]<intervals[j][0]
    })
    // Make a repeat 
    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])// Assign maximum 
            intervals=append(intervals[:i+1],intervals[i+2:]...)
            i--
        }
    }
    return intervals
}
func max(a,b int)int{
    if a>b{
        return a
    }
    return b
}

Complexity analysis

Time complexity ：O(nlogn), among n Is the number of intervals . Remove the cost of sorting , We only need one linear scan , So the main time cost is sorting O(nlogn).

Spatial complexity ：O(logn), among n Is the number of intervals . The calculation here is in addition to storing the answer , Extra space used .O(logn) That is, the space complexity required for sorting .