思路分析

一想到就是二路归并，但是这个复杂度肯定不符合题目要求。哎，自己是想不到新思路了，还是看题解。
二分找第k小的数，每次对两个数组取前k/2个数，比较最后一个。较小的数组可以保证这前k/2个数肯定都比第k小的数更小，因此可以舍弃，对于新的两个数组，递归求解第k小的数这一问题。（实际代码中通过修改起始索引位置形成新数组）
非常巧妙的一个思路，看懂后恍然大悟，但是实际实现过程中要充分考虑各种边界情况，比如其中一个数组为空时，k=1时。

代码实现

  1. public class Solution {
  2.     public double findMedianSortedArrays(int[] nums1, int[] nums2) {
  3.         int len1 = nums1.length;
  4.         int len2 = nums2.length;
  5.         // 统一奇偶数情况的表达形式
  6.         // 待求数据的索引顺序, 从小到大排列, 下标从1开始
  7.         int leftIndex = (len1 + len2 + 1) / 2;
  8.         int rightIndex = (len1 + len2 + 2) / 2;
  9.         int leftNum = getKthNum(leftIndex, nums1, nums2, 0, len1, 0, len2);
  10.         int rightNum = getKthNum(rightIndex, nums1, nums2, 0, len1, 0, len2);
  11.         return (leftNum + rightNum) / 2.0;
  12.     }
  14.     /**
  15.      * 求两个正序数组中第K小的数
  16.      *
  17.      * @param k     索引号
  18.      * @param nums1 数组1
  19.      * @param nums2 数组2
  20.      * @param head1 数组1头指针
  21.      * @param len1  数组1剩余长度
  22.      * @param head2 数组2头指针
  23.      * @param len2  数组2剩余长度
  24.      * @return 第K小的数
  25.      */
  26.     private int getKthNum(int k, int[] nums1, int[] nums2, int head1, int len1, int head2, int len2) {
  27.         // 如果有一组序列已被全部舍弃, 直接在另一组序列上即可确定
  28.         if (len1 == 0) {
  29.             return nums2[head2 + k - 1];
  30.         }
  31.         if (len2 == 0) {
  32.             return nums1[head1 + k - 1];
  33.         }
  34.         // 求第1小的数直接比较即可
  35.         if (k == 1) {
  36.             return Math.min(nums1[head1], nums2[head2]);
  37.         }
  38.         // 确定要舍弃的项数
  39.         int drop = Math.min(k / 2, Math.min(len1, len2));
  40.         int index1 = head1 + drop - 1;
  41.         int index2 = head2 + drop - 1;
  42.         // 同一索引上数值较小的序列, 前面的数值将被舍弃
  43.         if (nums1[index1] <= nums2[index2]) {
  44.             return getKthNum(k - drop, nums1, nums2, index1 + 1, len1 - drop, head2, len2);
  45.         } else {
  46.             return getKthNum(k - drop, nums1, nums2, head1, len1, index2 + 1, len2 - drop);
  47.         }
  48.     }
  49. }