This is the 19th day of my participation in the Gwen Challenge.More article challenges
For a better tomorrow, keep brushing LeetCode!
The title
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 2Copy the code
Example 2:
Input: nums1 = [1,2], nums2 = [3,4] output: 2.50000 description: merge array = [1,2,3,4], median (2 + 3) / 2 = 2.5Copy the code
Example 3:
Input: nums1 = [0,0], nums2 = [0,0] output: 0.00000Copy the code
Example 4:
Input: nums1 = [], nums2 = [1] Output: 1.00000Copy the code
Example 5:
Input: nums1 = [2], nums2 = [] Output: 2.00000Copy the code
Tip:
nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-106 <= nums1[i], nums2[i] <= 106
Copy the code
Solution 1 – merge arrays
Their thinking
The brute force solution is to merge the two arrays and find the median.
code
func findMedianSortedArrays(nums1, nums2 []int) float64 {
m, n := len(nums1), len(nums2)
nums := make([]int, m + n)
var i, j int
for k := 0; k < len(nums); k++ {
if i < m && j < n {
if nums1[i] < nums2[j] {
nums[k] = nums1[i]
i++
}else {
nums[k] = nums2[j]
j++
}
}else if i < m {
nums[k] = nums1[i]
i++
}else if j < n {
nums[k] = nums2[j]
j++
}
}
if len(nums) % 2= =0 {
return float64(nums[len(nums)/2] + nums[len(nums)/2- 1) /2
}
return float64(nums[len(nums)/2])}Copy the code
The execution result
Execution time: 16 ms beat 76.44% of users in all Go commits memory consumption: 5.7 MB beat 33.51% of users in all Go commitsCopy the code
Complexity analysis
- Time complexity: O(m+n)O(m+n)O(m+n)
- Space complexity: O(m+n)O(m+n)O(m+n)
Topic link
4. Find the median of two positive ordinal groups