题目描述

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。

请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。

你可以假设 nums1 和 nums2 不会同时为空。

示例 1:

  1. nums1 = [1, 3]
  2. nums2 = [2]
  4. 则中位数是 2.0

示例 2:

  1. nums1 = [1, 2]
  2. nums2 = [3, 4]
  4. 则中位数是 (2 + 3)/2 = 2.5

题解

暴力法：直接依大小顺序将 nums 插入到新的列表中即可。

  1. public static double FindMedianSortedArrays(int[] nums1, int[] nums2)
  2. {
  3.     var list = new List<int>();
  4.     for (int i = 0, j = 0; i < nums1.Length || j < nums2.Length;)
  5.     {
  6.         if (i >= nums1.Length)
  7.         {
  8.             list.Add(nums2[j]);
  9.             j++;
  10.             continue;
  11.         }
  12.         if (j >= nums2.Length)
  13.         {
  14.             list.Add(nums1[i]);
  15.             i++;
  16.             continue;
  17.         }
  19.         if (nums1[i] < nums2[j])
  20.         {
  21.             list.Add(nums1[i]);
  22.             i++;
  23.         }
  24.         else
  25.         {
  26.             list.Add(nums2[j]);
  27.             j++;
  28.         }
  29.     }
  31.     var halfIndex = list.Count / 2;
  32.     if (list.Count % 2 == 0)
  33.     {
  34.         return Convert.ToDouble(list[halfIndex] + list[halfIndex - 1]) / 2;
  35.     }
  37.     return Convert.ToDouble(list[halfIndex]);
  38. }