Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.The overall run time complexity should be O(log (m+n)). Example 1:Input: nums1 = [1,3], nums2 = [2]Output: 2.00000Explanation: merged array = [1,2,3] and median is 2.Example 2:Input: nums1 = [1,2], nums2 = [3,4]Output: 2.50000Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5. Constraints:nums1.length == mnums2.length == n0 <= m <= 10000 <= n <= 10001 <= m + n <= 2000-106 <= nums1[i], nums2[i] <= 106
Question
Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.The overall run time complexity should be O(log (m+n)). Example 1:Input: nums1 = [1,3], nums2 = [2]Output: 2.00000Explanation: merged array = [1,2,3] and median is 2.Example 2:Input: nums1 = [1,2], nums2 = [3,4]Output: 2.50000Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5. Constraints:nums1.length == mnums2.length == n0 <= m <= 10000 <= n <= 10001 <= m + n <= 2000-106 <= nums1[i], nums2[i] <= 106
Solution
This problem can be solved using a binary search algorithm. Here are the steps:
- If the length of nums1 is greater than the length of nums2, swap them.
- Initialize the variables imin and imax to 0 and the length of the smaller array, respectively.
- While imin is less than or equal to imax, do the following:
- Calculate the middle index i of the smaller array and the corresponding index j of the larger array such that i + j equals the half length of the combined array.
- If the i-th element of the smaller array is less than the j-1-th element of the larger array, set imin to i + 1.
- Otherwise, if the i-1-th element of the smaller array is greater than the j-th element of the larger array, set imax to i - 1.
- Otherwise, both i and j are at the correct positions.
- If i and j are at the correct positions, do the following:
- If the combined array has an odd length, return the maximum of the i-1-th element of the smaller array and the j-1-th element of the larger array.
- Otherwise, return the average of the maximum of the i-1-th element of the smaller array and the j-1-th element of the larger array, and the minimum of the i-th element of the smaller array and the j-th element of the larger array.
- If imin is greater than the length of the smaller array, return the j-th element of the larger array.
- Otherwise, return the i-th element of the smaller array.
This algorithm ensures that the time complexity is O(log(min(m, n))) where m and n are the lengths of nums1 and nums2, respectively.
Similar Questions
You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.Merge nums1 and nums2 into a single array sorted in non-decreasing order.The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n. Example 1:Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3Output: [1,2,2,3,5,6]Explanation: The arrays we are merging are [1,2,3] and [2,5,6].The result of the merge is [1,2,2,3,5,6] with the underlined elements coming from nums1.Example 2:Input: nums1 = [1], m = 1, nums2 = [], n = 0Output: [1]Explanation: The arrays we are merging are [1] and [].The result of the merge is [1].Example 3:Input: nums1 = [0], m = 0, nums2 = [1], n = 1Output: [1]Explanation: The arrays we are merging are [] and [1].The result of the merge is [1].Note that because m = 0, there are no elements in nums1. The 0 is only there to ensure the merge result can fit in nums1. Constraints:nums1.length == m + nnums2.length == n0 <= m, n <= 2001 <= m + n <= 200-109 <= nums1[i], nums2[j] <= 109 Follow up: Can you come up with an algorithm that runs in O(m + n) time?
Given two sorted arrays arr1[] and arr2[] of sizes n and m in non-decreasing order. Merge them in sorted order without using any extra space. Modify arr1 so that it contains the first N elements and modify arr2 so that it contains the last M elements.
What is the time complexity for executing merge sort on an array of size n which is already sorted isSelect one:O(n log n)O(log n)OO(n^2)
Consider the following array: array = [38, 27, 43, 3, 9, 82, 10].Using merge sort – the first round of the merge sort algorithm will be [38] [27] [43] [3] [9] [82] [10].What will the second round of the merge sort algorithm be:a.[27, 38], [3, 43], [9, 82], [10]b.[38, 27], [43, 3], [82, 9], [10]c.[38,27,43],[3,9,82] , [10]d.[3,27,38], [9,43,82,10]
You are given an integer array nums. The uniqueness array of nums is the sorted array that contains the number of distinct elements of all the subarrays of nums. In other words, it is a sorted array consisting of distinct(nums[i..j]), for all 0 <= i <= j < nums.length.Here, distinct(nums[i..j]) denotes the number of distinct elements in the subarray that starts at index i and ends at index j.Return the median of the uniqueness array of nums.Note that the median of an array is defined as the middle element of the array when it is sorted in non-decreasing order. If there are two choices for a median, the smaller of the two values is taken. Example 1:Input: nums = [1,2,3]Output: 1Explanation:The uniqueness array of nums is [distinct(nums[0..0]), distinct(nums[1..1]), distinct(nums[2..2]), distinct(nums[0..1]), distinct(nums[1..2]), distinct(nums[0..2])] which is equal to [1, 1, 1, 2, 2, 3]. The uniqueness array has a median of 1. Therefore, the answer is 1.Example 2:Input: nums = [3,4,3,4,5]Output: 2Explanation:The uniqueness array of nums is [1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3]. The uniqueness array has a median of 2. Therefore, the answer is 2.Example 3:Input: nums = [4,3,5,4]Output: 2Explanation:The uniqueness array of nums is [1, 1, 1, 1, 2, 2, 2, 3, 3, 3]. The uniqueness array has a median of 2. Therefore, the answer is 2. Constraints:1 <= nums.length <= 1051 <= nums[i] <= 105
Upgrade your grade with Knowee
Get personalized homework help. Review tough concepts in more detail, or go deeper into your topic by exploring other relevant questions.