The title

  • Given two positively ordered (from small to large) arrays nums1 and nums2 of size m and n, respectively. Find and return the median of these two ordinal groups.

LeetCode link

Answer key

  • The more general form of this problem is, given two sorted arrays, find the KTH smallest element of all the elements in both arrays, and all the elements are allowed to repeat;
  • Method 1: Merge two arrays directly, and then find the KTH smallest element, algorithm complexity O(m+n);
  • Method 2: similar to the merge sort, use two Pointers pA and pB, respectively. If the current element of array A is small, then pA++, and m++; If the current element of array B is small, then pB++ and m++. When m is equal to k, we find the KTH smallest element;
  • Method 3: Find the KTH smallest number. If you can delete a number smaller than k every time, you only need to delete k times. How to use the ordered array, the first time delete k/2, the second time delete K /4… , it should be noted that the number of output cannot be longer than the length of the current array. The details are as follows: Assuming that the number of elements of A and B is greater than k/2, compare A[k/2-1] of array A with B[k/2-1] of array B. There are three cases.
  1. A[k/2-1]
  2. A/k / 2-1 = = B/k / 2-1, by allowing repeat, thus found the first k decimal, for k / 2-1 A or B/k / 2-1;
  3. A[k/2-1]>B[K /2-1], similar to case 1.
  • After removing k/2 elements, we can now recursively find the k/2 decimal in the remaining elements, but note the recursive exit condition.
  1. If A or B is null, return B[k-1] or A[k-1];
  2. Return min(A[0], B[0]) when k==1;
  3. Return A[k/2-1] or B[k/2-1] when A[k/2-1]==B[k/2-1].

The source code

int find_kth(int* nums1, int nums1Size, int* nums2, int nums2Size, int k);

double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size){
    int total = nums1Size + nums2Size;
	if (total & 0x1)
	{
		return find_kth(nums1, nums1Size, nums2, nums2Size, total / 2 + 1) / 1.0;
	}
	else
	{
		return (find_kth(nums1, nums1Size, nums2, nums2Size, total / 2) + find_kth(nums1, nums1Size, nums2, nums2Size, total / 2 + 1)) / 2.0; }}int find_kth(int* nums1, int nums1Size, int* nums2, int nums2Size, int k)
{
	if (nums1Size > nums2Size)
	{
		return find_kth(nums2, nums2Size, nums1, nums1Size, k);
	}
	if (nums1Size == 0)
	{
		return nums2[k - 1];
	}
	if (k == 1)
	{
		return nums1[k - 1] < nums2[k - 1]? nums1[k -1] : nums2[k - 1];
	}
	int ia = k/2 <nums1Size ? k / 2 : nums1Size;
	int ib = k - ia;
	if (nums1[ia - 1] > nums2[ib - 1])
	{
		return find_kth(nums1, nums1Size, nums2 + ib, nums2Size - ib, k - ib);
	}
	else if (nums1[ia - 1] < nums2[ib - 1])
	{
		return find_kth(nums1 + ia, nums1Size - ia, nums2, nums2Size, k - ia);
	}
	else
	{
		return nums1[ia - 1]; }}Copy the code