Median Of Two Sorted Arrays

Introduction

Leet Code 4: Median of Two Sorted Arrays 解題報告(solution report)

Use C language to solve the problem.

Problem Description

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.

The overall run time complexity should be O(log (m+n)).

Example 1:

Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
Explanation: merged array = [1,2,3] and median is 2.

Example 2:

Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000
Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.

Constraints:

• nums1.length == m
• nums2.length == n
• 0 <= m <= 1000
• 0 <= n <= 1000
• 1 <= m + n <= 2000
• -106 <= nums1[i], nums2[i] <= 106

Score

0ms | 11.24MB

Solution

話不多說先奉上解題程式碼

C Solution

int findIT(int *nums1,int nums1Size,int *nums2,int nums2Size,int medd){
        int result = 0;
        for(int a=0,b=0;(a+b)<medd;){
                if(b<nums2Size&&a<nums1Size&&nums1[a]>nums2[b]){
                        result = nums2[b++];
                }else{
                        if(a<nums1Size)result = nums1[a++];
                        else result = nums2[b++];
                }
        }
        return result;
}
double findMedianSortedArrays(int *nums1,int nums1Size,int *nums2,int nums2Size){
        int size = nums1Size+nums2Size;
        int medd = size>>1;
        int meda = medd+1;
        int medb = medd-1;
        double r = 0;
        if(size&1){
                if(nums1Size==0)return nums2[medd];
                else if(nums2Size==0)return nums1[medd];
                return findIT(nums1,nums1Size,nums2,nums2Size,meda);
        }
        if(nums1Size==0){
                r = nums2[medd]+nums2[medb];
        }else if(nums2Size==0){
                r = nums1[medd]+nums1[medb];
        }else{
            r = findIT(nums1,nums1Size,nums2,nums2Size,meda)+findIT(nums1,nums1Size,nums2,nums2Size,medd);
        }
        return r/2;
}