题解 | #牛的体重排序#

1. 题目考察的知识点

二分查找

2. 题目解答方法的文字分析

如何把时间复杂度降低到 O(log⁡(m+n))呢？如果对时间复杂度的要求有 log，通常都需要用到二分查找，这道题也可以通过二分查找实现。即首先计算出两个数组的总长度totallen，然后判断出总长度是奇数还是偶数。如果是奇数根据中位数的定义，当 totallen 是奇数时，中位数是两个有序数组中的第 totallen/2 个元素，当 totallen 是偶数时，中位数是两个有序数组中的第 totallen/2个元素和第 totallen/2+1 个元素的平均值。因此，这道题可以转化成寻找两个有序数组中的第 k 小的数，其中 k为 totallen/2 或 totallen/2+1。

getKthElement方法就是用来寻找两个有序数组中的第 k 小的数。

3. 本题解析所用的编程语言

java

4. 完整且正确的编程代码

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param weightsA int整型一维数组 
     * @param weightsB int整型一维数组 
     * @return double浮点型
     */
    public double findMedianSortedArrays (int[] weightsA, int[] weightsB) {
        int len1= weightsA.length;
        int len2=weightsB.length;
        int totallen = len1+len2;
        if(totallen%2==1){
            int midIndex = totallen/2;
            double median=getKthElement(weightsA,weightsB,midIndex+1);
            return median;
        }else{
            int midIndex1 = totallen/2-1,midIndex2=totallen/2;
            double median=(getKthElement(weightsA, weightsB, midIndex1 + 1) + getKthElement(weightsA, weightsB, midIndex2 + 1)) / 2.0;
            return median;
        }
    }
    public int getKthElement(int[] nums1,int[] nums2,int k){
        int length1 = nums1.length, length2 = nums2.length;
        int index1 = 0, index2 = 0;
        int kthElement = 0;

        while (true) {
            // 边界情况
            if (index1 == length1) {
                return nums2[index2 + k - 1];
            }
            if (index2 == length2) {
                return nums1[index1 + k - 1];
            }
            if (k == 1) {
                return Math.min(nums1[index1], nums2[index2]);
            }
            
            // 正常情况
            int half = k / 2;
            int newIndex1 = Math.min(index1 + half, length1) - 1;
            int newIndex2 = Math.min(index2 + half, length2) - 1;
            int pivot1 = nums1[newIndex1], pivot2 = nums2[newIndex2];
            if (pivot1 <= pivot2) {
                k -= (newIndex1 - index1 + 1);
                index1 = newIndex1 + 1;
            } else {
                k -= (newIndex2 - index2 + 1);
                index2 = newIndex2 + 1;
            }
        }
  
    }
    }