刷题LeetCode4。寻找两个正序数组的中位数

　　题目链接：
　　力扣
　　题目描述
　　给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。
　　请你找出并返回这两个正序数组的 中位数 。算法的时间复杂度应该为 O(log (m+n))  题目分析
　　常规思路：
　　1.合并两个数组再排序，时间复杂度O(m+n)，空间复杂度O(m+n)
　　2.归并排序，时间复杂度O(m+n)，空间复杂度O(1)
　　本题解题思路应该如何呢？
　　根据题目中时间复杂度，可以考虑采用二分查找，这也是本题的难度所在。
　　假设两个有序数组分别是 A 和 B，两数组的总长度为 totalLength： 两数组总长度（totalLength）为奇数：中位数下标(midIndex)=totalLength/2，中位数=下标midIndex所在数； 两数组总长度（totalLength）为偶数，中位数下标有两个 midIndex1，midIndex2， midIndex1=totalLength/2-1 ，midIndex2=totalLength/2，中位数=(下标midIndex1所在数+下标midIndex2所在数)/2；
　　注意：midIndex，为两数组合并后的下标，并不是真的将两个数组进行合并，大家要搞清楚这个概念。
　　这个时候，问题转化为找到数组 A 和 B 中的第 k 大元素（kElement），那怎么找到呢？
　　可以比较 A[k/2-1] 与B[k/2-1] ： A[k/2 1]<=B[k/2 1]，则数组A中，下标为 0 至 k/2 1 的元素均小于kElement，可以排除这部分元素； A[k/2 1]>B[k/2 1]，则数组B中，下标为 0 至 k/2 1 的元素均小于kElement，可以排除这部分元素；
　　很容易想到，查找范围缩小了一半，可以在排除后的新数组上继续进行二分查找，并且根据我们排除数的个数，减少 k 的值（因为我们排除的数都不大于第k 小的数）。需要注意以下几种情况：
　　1.保证数组不越界；
　　2.如果一个数组为空，说明该数组中的所有元素都被排除，我们可以直接返回另一个数组中第k小的元素；
　　3.若 k=1，只要返回两个数组首元素的最小值即可。代码实现时间复杂度：O(log (m+n)) 空间复杂度：O(1) public class FindMedianSortedArrays_4 {       /**      * 常规思路：      * 《1》合并两个数组在排序      * 《2》归并排序      *      * @param args      */      public static void main(String[] args) {         int[] num1 = {1, 3};         int[] num2 = {2};         //int[] num1 = {1, 3,4,9};         //int[] num2 = {1,2,3,4,5,6,7,8,9};         FindMedianSortedArrays_4 findMedianSortedArrays_4 = new FindMedianSortedArrays_4();         findMedianSortedArrays_4.findMedianSortedArrays(num1, num2);      }       /**      * 二分查找，巧妙      * 时间复杂度：O(log (m+n))      * 空间复杂度：O(1)      *      * @param nums1      * @param nums2      * @return      */     public double findMedianSortedArrays(int[] nums1, int[] nums2) {         int length1 = nums1.length;         int length2 = nums2.length;         int totalLength = length1 + length2;           // 两数组总长度（totalLength）为奇数，中位数下标(midIndex)=totalLength/2，中位数=下标k所在数         if (totalLength % 2 == 1) {             System.out.println(＂两数组总长度（totalLength）为奇数＂);             int midIndex = totalLength / 2;              double median = getKthElement(nums1, nums2, midIndex + 1);             System.out.println(＂median:＂ + median);             return median;          } else {             // 两数组总长度（totalLength）为偶数，中位数下标有两个 midIndex1，midIndex2， midIndex1=totalLength/2-1 ，midIndex2=totalLength/2，             // 中位数=(下标midIndex1所在数+下标midIndex2所在数)/2             System.out.println(＂两数组总长度（totalLength）为偶数＂);              int midIndex1 = totalLength / 2 - 1, midIndex2 = totalLength / 2;             double median = (getKthElement(nums1, nums2, midIndex1 + 1) + getKthElement(nums1, nums2, midIndex2 + 1)) / 2.0;             System.out.println(＂median:＂ + median);              return median;          }     }      /**      * 获取第k小的元素      *      * @param nums1      * @param nums2      * @param k      * @return      */     public int getKthElement(int[] nums1, int[] nums2, int k) {         System.out.println(＂初始k:＂ + k);          int length1 = nums1.length;         int length2 = nums2.length;           // 用来记录两个数组寻找第k小元素的起始下标         int index1 = 0, index2 = 0;           while (true) {             // 边界情况，数组1为空，只需要考虑数组2             if (index1 == length1) {                 return nums2[index2 + k - 1];             }             // 边界情况，数组2为空，只需要考虑数组1             if (index2 == length2) {                 return nums1[index1 + k - 1];             }              if (k == 1) {                 return Math.min(nums1[index1], nums2[index2]);             }              // 比较 num1[k/2-1] 与 num1[k/2-1]             int compareIndex1 = Math.min(index1 + k / 2, length1) - 1;             int compare1 = nums1[compareIndex1];             int compareIndex2 = Math.min(index2 + k / 2, length2) - 1;             int compare2 = nums2[compareIndex2];              if (compare1 < compare2) {                  k -= compareIndex1 - index1 + 1;                  index1 = compareIndex1 + 1;               } else {                 k -= compareIndex2 - index2 + 1;                 index2 = compareIndex2 + 1;              }             System.out.println(＂compare1:＂ + compare1);             System.out.println(＂compare2:＂ + compare2);             System.out.println(＂index1:＂ + index1);             System.out.println(＂index2:＂ + index2);             System.out.println(＂k:＂ + k);           }      }   }
　　注意：while语句中是最核心的部分，也就是二分查找的主要思想。
　　好了，今天就到这里，感谢各位看官到这里，不如点个关注吧！