Leetcode divide and conquer / dichotomy

q23 Merge k A sort list

Subject portal

Answer key

Use the idea of partition to solve , Merge sort . Because there is k A linked list , So traverse the linked list array , Then sort them one by one .

func mergeKLists(lists []*ListNode) *ListNode {
    
	if len(lists) == 0 {
    
		return nil
	}
	if len(lists) == 1 {
    
		return lists[0]
	}
	var L *ListNode
	L = mergeList(lists[0], lists[1])
	for i := 2; i < len(lists); i++ {
    
		L = mergeList(L, lists[i])
	}
	return L
}

func mergeList(L1, L2 *ListNode) *ListNode {
    
	L := &ListNode{
    }
	curr := L
	var next *ListNode
	for L1 != nil && L2 != nil {
    
		if L1.Val < L2.Val {
    
			next = L1.Next
			curr.Next = L1
			L1.Next = nil
			L1 = next
		} else {
    
			next = L2.Next
			curr.Next = L2
			L2.Next = nil
			L2 = next
		}
		curr = curr.Next
	}
	if L1 != nil {
    
		curr.Next = L1
	}
	if L2 != nil {
    
		curr.Next = L2
	}
	return L.Next
}

q33 Search rotation sort array

Subject portal

Answer key

In this question , Arrays are not globally ordered , But partial order , But it can still be solved by dichotomy .
You can find that when we rotate the array , There must be a part of the array that is ordered , For example, in the example ： The array becomes [4, 5, 6] and [7, 0, 1, 2] Two parts , And the left side of it [4, 5, 6] The array of this part is ordered .
So in the loop, we can check the mid Separate sides , Which side is orderly , And decide target Is it on the orderly side , If not on the orderly side , It must be on the other side . Through this idea, we finally get the answer .

func search(nums []int, target int) int {
    
	n := len(nums)
	if n == 0 {
    
		return -1
	}
	if n == 1 {
    
		if target == nums[0] {
    
			return 0
		} else {
    
			return -1
		}
	}
	l, r := 0, n - 1
	for l <= r {
    
		mid := (l + r) / 2
		if nums[mid] == target {
    
			return mid
		}
		//  If the left side is in order 
		if nums[0] <= nums[mid] {
    
			//  If target Just in the left section 
			if nums[0] <= target && target < nums[mid] {
    
				r = mid - 1
			} else {
    
				l = mid + 1
			}
		//  If the right side is in order 
		} else {
    
			//  If target Just in the right section 
			if nums[mid] < target && target <= nums[n - 1] {
    
				l = mid + 1
			} else {
    
				r = mid - 1
			}
		}
	}
	return -1
}

q34 Find the first and last positions of the elements in the sort array

Subject portal

Answer key

First use two points to find the value target The subscript midIndex, And then to midIndex Is the midpoint , Look left and right for target The left and right borders of .

func searchRange(nums []int, target int) []int {
    
	l, r, midIndex, n := 0, len(nums) - 1, -1, len(nums)
	for l <= r {
    
		mid := (l + r) / 2
		if nums[mid] == target {
    
			midIndex = mid
			break
		}
		if nums[mid] < target && target <= nums[n - 1] {
    
			l = mid + 1
		} else {
    
			r = mid - 1
		}
	}
	if midIndex == -1 {
    
		return []int{
    -1, -1}
	}

	start, end := 0, 0
	for i := midIndex; i >= 0; i--{
    
		if nums[i] == target {
    
			start = i
		} else {
    
			break
		}
	}
	for i := midIndex; i <= n - 1; i++{
    
		if nums[i] == target {
    
			end = i
		} else {
    
			break
		}
	}
	return []int{
    start, end}
}