4. Find the median of two positive ordinal groups

Given two positive-ordered (from small to large) arrays of size m and n, nums1 and nums2. Please find and return the median of the two positive ordinal groups.

Example 1:

Input: nums1 = [1,3], nums2 = [2] output: 2.00000 explanation: merge array = [1,2,3], median 2

Example 2:

Input: nums1 = [1,2], nums2 = [3,4] output: 2.50000 description: merge array = [1,2,3,4], median (2 + 3) / 2 = 2.5

Source: LeetCode link: leetcode-cn.com/problems/me… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Go array = Go array = Go array

  1. Array declaration and initialization

    // Declare an array arR
var arr [3] int
arr := []int{1.2.3}
Copy the code

  2. Access array elements, very similar to C language.

    b := arr[1]
Copy the code

  3. Use arrays in the function:

    In Go, [2]int is not the same type as []int. In other words, passing an array of type [2]int will not compile if the parameter is []int. For example, the following code is illegal:

    package main

func main(a)  {
	var arr [3] int
	arr2 := []int{1.2.3}
    Cannot use arr (type [3]int) as type []int in argument to printArray1
	printArray1(arr)
    Cannot use arr2 (type []int) as type [3]int in argument to printArray2
    printArray2(arr2)
}

func printArray1(arr []int) {
	for _, v := range arr {
		println(v)
	}
}
func printArray2(arr [3]int) {
	for _, v := range arr {
		println(v)
	}
}
Copy the code

  4. Dynamic length array

    length := 3
arr := make([]int, length)
Copy the code

Back to the problem, let’s use method 4 to solve it.

Solution 1: quickly merge two groups of positive Ordinal Numbers, and then find the median of the combined array.
/** * solution 1: use two subscripts P1, p2, quickly merge two arrays into a large array of length (m+n); If (m+n) is odd, the number of positions subscript (m+n)/2 is the median; If (m+n) is even, the mean of subscripts (m+n)/ 2-1 and (m+n)/2 is the median */
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
	mergeArray := mergeArray(nums1, nums2)
	for _, v := range mergeArray {
		println(v)
	}
	length := len(mergeArray)
	if length % 2= =0 {
		/ / even
		return float64((mergeArray[length/2- 1] + mergeArray[length/2) /])2
	} else {
		/ / odd
		return float64(mergeArray[length/2])}}/** * merge string */
func mergeArray(nums1 []int, nums2 []int) []int {
	length1 := len(nums1)
	length2 := len(nums2)
	// Error 1: non-constant array bound length1 + length2
	Length1 := [length1 + length2]int
	mergeArray := make([]int, length1 + length2)
	mergeArrayP := 0
	p1 := 0
	p2 := 0
	for ; p1 < length1 || p2 < length2 ; {
		if p1 >= length1 {
			mergeArray[mergeArrayP] = nums2[p2]
			p2++
			mergeArrayP ++
			continue
		}

		if p2 >= length1 {
			mergeArray[mergeArrayP] = nums1[p1]
			p1++
			mergeArrayP ++
			continue
		}

		if nums1[p1] < nums2[p2] {
			mergeArray[mergeArrayP] = nums1[p1]
			p1 ++
			mergeArrayP ++
		} else {
			mergeArray[mergeArrayP] = nums2[p2]
			p2 ++
			mergeArrayP ++
		}
	}
	return mergeArray
}
Copy the code

Solution 2: Do not merge arrays, just move through Pointers to two arrays. Very similar to solution 1, I won’t write the code here.

Find the KTH smallest number in two ordered arrays, where k is (m+n)/2(m+n)/2 or (m+n)/2+1.

Solution 4: Divide an array, which is a mathematical way to reduce the complexity of time controls. See the official website for details.

Go language power buckle brush series of articles | Go theme month

  1. Go language power buckle brush – the sum of two numbers | Go theme month

  2. Go language power buckle brush – add two numbers | Go theme months

  3. Go language power button brush title – the largest string without repeating characters | Go theme month