跳转至

LeetCode: 4. 两个排序数组的中位数

两个排序数组的中位数

1、问题描述

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Example 1:
nums1 = [1, 3]
nums2 = [2]

The median is 2.0
Example 2:
nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

​ 给定两个大小为 m 和 n 的有序数组 nums1nums2

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

示例 1:

nums1 = [1, 3]
nums2 = [2]

中位数是 2.0

示例 2:

nums1 = [1, 2]
nums2 = [3, 4]

中位数是 (2 + 3)/2 = 2.5

2、解题思路

2.1 使用二分查找法

double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {
/*
*   基本思想:
*       每一次判断,要找的是第k个数,如果在数组1中,第k/2个数比数组个数还要大,就是用最后一个数
        用两个数组中的第k/2个数进行比较,如果第一个数组中的比第二个数组中的大,就能够将第二个数组中前k/2个数排除在比较范围之外
        这时候,要查找的的就不是第k个数,而是k-k/2个数,
*
*
*   left1:表示数组1的左边界,数组下标
*   left2:表示数组2的左边界,数组下标
*/
    int mid_loc;
    int pos1, pos2, left1 = 0, left2 = 0;
    // 奇偶判断,奇数为真,偶数为假
    bool flag_odd_even = (nums1Size + nums2Size) % 2 == 0 ? false : true;
    bool found = false;
    double result;
    int result_pos;
    // 根据奇偶数,判断中位数是第几位数
    if (flag_odd_even) {
        //如果是奇数
        mid_loc = (nums1Size + nums2Size) / 2 + 1;
    } else {
        //如果是偶数
        mid_loc = (nums1Size + nums2Size) / 2;
    }

    // 判断几种特殊情况,可以直接返回结果
    if (nums1Size == 0 && nums2Size != 0 && nums2Size > mid_loc) {
        if (flag_odd_even) {
            result = nums2[mid_loc - 1];
        } else {
            result = (1.0 * nums2[mid_loc - 1] + nums2[mid_loc]) / 2;
        }
    } else if (nums2Size == 0 && nums1Size != 0 && nums1Size > mid_loc) {
        if (flag_odd_even) {
            result = nums1[mid_loc - 1];
        } else {
            result = (1.0 * nums1[mid_loc - 1] + nums1[mid_loc]) / 2;

        }
    } else {
        // 使用二分法,进行判断
        while (!found) {

            pos1 = (mid_loc / 2) > (nums1Size - left1 - 1) ? nums1Size - 1 : (mid_loc / 2 + left1 - 1);
            pos2 = (mid_loc / 2) > (nums2Size - left2 - 1) ? nums2Size - 1 : (mid_loc / 2 + left2 - 1);

            if (nums1[pos1] >= nums2[pos2]) {
                // 如果第二个已经到了边界, 在第一个数组中直接找到结果
                if (pos2 == (nums2Size - 1)) {
                    result_pos = mid_loc - (pos2 - left2 + 1) + left1 - 1;
                    //奇数
                    if (flag_odd_even) {

                        result = nums1[result_pos];
                    } else {
                        result = (1.0 * nums1[result_pos] + nums1[result_pos + 1]) / 2;
                    }
                    found = true;
                } else {

                    mid_loc -= (pos2 - left2 + 1);
                    left2 = pos2 + 1;
                }
            } else {
                // 如果第一个到了边界,直接在第二个数组中找到结果
                if (pos1 == (nums1Size - 1)) {
                    result_pos = mid_loc - (pos1 - left1 + 1) + left2 - 1;
                    //奇数
                    if (flag_odd_even) {
                        result = nums2[result_pos];
                    } else {
                        result = (1.0 * nums2[result_pos] + nums2[result_pos + 1]) / 2;
                    }
                    found = true;

                } else {
                    mid_loc -= (pos1 - left1 + 1);
                    left1 = pos1 + 1;
                }
            }
            if (!found && mid_loc == 1) {

                if (nums1[left1] <= nums2[left2]) {
                    // 如果是奇数
                    if (flag_odd_even) {
                        result = nums1[left1];
                    } else {
                        // 第一个条件是边界保护
                        if ((left1 < nums1Size - 1) && (nums1[left1 + 1] <= nums2[left2])) {
                            result = (1.0 * nums1[left1] + nums1[left1 + 1]) / 2;
                        } else {
                            result = (1.0 * nums1[left1] + nums2[left2]) / 2;
                        }
                    }
                } else {
                    if (flag_odd_even) {
                        result = nums2[left2];
                    } else {
                        // 第一个条件是边界保护
                        if ((left2 < nums2Size - 1) && (nums2[left2 + 1] <= nums1[left1])) {
                            result = (1.0 * nums2[left2] + nums2[left2 + 1]) / 2;
                        } else {
                            result = (1.0 * nums2[left2] + nums1[left1]) / 2;

                        }
                    }

                }
                found = true;
            }
        }
    }
    return result;
}

2.2 缓冲数组法

​ 这个缓冲法就有点笨拙了,就类似于归并排序里面的,将两个已排好序的数组合并起来,不过我们只需要其中一半即可,这样就找到中位数了,这种办法的好处就是思路非常清晰,简单,但是会占用额外的空间,并且速度不快;

double findMedianSortedArrays(int *nums1, int nums1Size, int *nums2, int nums2Size) {
/*
*   基本思想:
*
*
*/

    int buff_length = (nums1Size + nums2Size) / 2 + 1;
    int num = (int*)malloc(sizeof(int)*buff_length);
    bool flag_odd_even = (nums1Size + nums2Size) % 2 == 0 ? false : true;
    int i=0,j=0;
    int count = 0;
    double result;
    int temp_length = buff_length;
    while (temp_length-- ){
        if ((i <nums1Size && nums1[i] <= nums2[j]) || j>= nums2Size ){
            num[count++] = nums1[i];
            i++;
        }else if((j < nums2Size && nums2[j] <= nums1[i]) || i >= nums1Size){
            num[count++] = nums2[j];
            j++;
        }
    }

    if (flag_odd_even){
        result = num[buff_length-1];
    } else{
        result = (1.0 * num[buff_length-2] + num[buff_length-1])/2;
    }

    return result;

}