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

　　题目链接：
　　力扣
　　题目描述
　　给定两个大小分别为m和n的正序（从小到大）数组nums1和nums2。
　　请你找出并返回这两个正序数组的中位数。算法的时间复杂度应该为O（log（mn））题目分析
　　常规思路：
　　1。合并两个数组再排序，时间复杂度O（mn），空间复杂度O（mn）
　　2。归并排序，时间复杂度O（mn），空间复杂度O（1）
　　本题解题思路应该如何呢？
　　根据题目中时间复杂度，可以考虑采用二分查找，这也是本题的难度所在。
　　假设两个有序数组分别是A和B，两数组的总长度为totalLength：两数组总长度（totalLength）为奇数：中位数下标（midIndex）totalLength2，中位数下标midIndex所在数；两数组总长度（totalLength）为偶数，中位数下标有两个midIndex1，midIndex2，midIndex1totalLength21，midIndex2totalLength2，中位数（下标midIndex1所在数下标midIndex2所在数）2；
　　注意：midIndex，为两数组合并后的下标，并不是真的将两个数组进行合并，大家要搞清楚这个概念。
　　这个时候，问题转化为找到数组A和B中的第k大元素（kElement），那怎么找到呢？
　　可以比较A〔k21〕与B〔k21〕：A〔k21〕B〔k21〕，则数组A中，下标为0至k21的元素均小于kElement，可以排除这部分元素；A〔k21〕B〔k21〕，则数组B中，下标为0至k21的元素均小于kElement，可以排除这部分元素；
　　很容易想到，查找范围缩小了一半，可以在排除后的新数组上继续进行二分查找，并且根据我们排除数的个数，减少k的值（因为我们排除的数都不大于第k小的数）。需要注意以下几种情况：
　　1。保证数组不越界；
　　2。如果一个数组为空，说明该数组中的所有元素都被排除，我们可以直接返回另一个数组中第k小的元素；
　　3。若k1，只要返回两个数组首元素的最小值即可。代码实现时间复杂度：O（log（mn））空间复杂度：O（1）publicclassFindMedianSortedArrays4｛常规思路：《1》合并两个数组在排序《2》归并排序paramargspublicstaticvoidmain（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｝；FindMedianSortedArrays4findMedianSortedArrays4newFindMedianSortedArrays4（）；findMedianSortedArrays4。findMedianSortedArrays（num1，num2）；｝二分查找，巧妙时间复杂度：O（log（mn））空间复杂度：O（1）paramnums1paramnums2returnpublicdoublefindMedianSortedArrays（int〔〕nums1，int〔〕nums2）｛intlength1nums1。intlength2nums2。inttotalLengthlength1length2；两数组总长度（totalLength）为奇数，中位数下标（midIndex）totalLength2，中位数下标k所在数if（totalLength21）｛System。out。println（两数组总长度（totalLength）为奇数）；intmidIndextotalLength2；doublemediangetKthElement（nums1，nums2，midIndex1）；System。out。println（median：median）；｝else｛两数组总长度（totalLength）为偶数，中位数下标有两个midIndex1，midIndex2，midIndex1totalLength21，midIndex2totalLength2，中位数（下标midIndex1所在数下标midIndex2所在数）2System。out。println（两数组总长度（totalLength）为偶数）；intmidIndex1totalLength21，midIndex2totalLength2；doublemedian（getKthElement（nums1，nums2，midIndex11）getKthElement（nums1，nums2，midIndex21））2。0；System。out。println（median：median）；｝｝获取第k小的元素paramnums1paramnums2paramkreturnpublicintgetKthElement（int〔〕nums1，int〔〕nums2，intk）｛System。out。println（初始k：k）；intlength1nums1。intlength2nums2。用来记录两个数组寻找第k小元素的起始下标intindex10，index20；while（true）｛边界情况，数组1为空，只需要考虑数组2if（index1length1）｛returnnums2〔index2k1〕；｝边界情况，数组2为空，只需要考虑数组1if（index2length2）｛returnnums1〔index1k1〕；｝if（k1）｛returnMath。min（nums1〔index1〕，nums2〔index2〕）；｝比较num1〔k21〕与num1〔k21〕intcompareIndex1Math。min（index1k2，length1）1；intcompare1nums1〔compareIndex1〕；intcompareIndex2Math。min（index2k2，length2）1；intcompare2nums2〔compareIndex2〕；if（compare1compare2）｛kcompareIndex1index11；index1compareIndex11；｝else｛kcompareIndex2index21；index2compareIndex21；｝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语句中是最核心的部分，也就是二分查找的主要思想。
　　好了，今天就到这里，感谢各位看官到这里，不如点个关注吧！