Leetcode笔记10-寻找两个正序数组的中位数

题目描述

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n)) 。

思路

1）最明显的思路是将两个数组进行合并，然后直接查找中位数
2）第二个方法是用两个指针分别指向两个数组，比较大小，小的向后移一位，从而找到中位数所在的位置，就不需要将两个数组全部进行排序，而变成了查找第(m+n)/2个数。当然实际情况想象的复杂一些，比如考虑到是否存在空数组、是否有一个数组中的指针移动到了最后还是没有找到中位数、当总数为偶数时前一个中位数的下一个数应该是哪个指针所指的数（还要考虑指针是否到了数组尾部）…
总而言之，第二种方法实现起来比较复杂，考虑的东西更多，我也是在多次提交报错之后才完整考虑了所有的情况。所以最后修改的自己可能也有点看不懂了。。

实现代码

double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size){
    int count=nums1Size+nums2Size;
    int mid=count/2;
    int i=0,j=0;
    if(nums1Size==0){
        if(nums2Size%2==0){
            return (nums2[nums2Size/2-1]+nums2[nums2Size/2])/2.0;
        } else{
            return nums2[nums2Size/2];
        }
    }
    if(nums2Size==0){
        if(nums1Size%2==0){
            return (nums1[nums1Size/2-1]+nums1[nums1Size/2])/2.0;
        } else{
            return nums1[nums1Size/2];
        }
    }
    if(count%2==1){        
        while((i+j)<mid&&i<nums1Size&&j<nums2Size){
            if(nums1[i]<nums2[j]){
                i++;
            }else{
                j++;
            }
        }       
        if(i==nums1Size){
            i--;
            while((i+j)<mid-1){
                j++;
            }
            return nums2[j];
        }else if(j==nums2Size){
            j--;
            while((i+j)<mid-1){
                i++;
            }
            return nums1[i];
        }else {
            if(nums1[i]<nums2[j]){
                return nums1[i];
            }else{
                return nums2[j];
            }            
        }
        
    }else{        
        while((i+j)<(mid-1)&&i<nums1Size&&j<nums2Size){
            if(nums1[i]<nums2[j]){
                i++;
            }else{
                j++;
            }
        }       
        if(i==nums1Size){
            i--;
            while((i+j)<mid){
                j++;
            }
            return (nums2[j-1]+nums2[j-2])/2.0;
        }else if(j==nums2Size){
            j--;
            while((i+j)<mid){
                i++;
            }
            return (nums1[i-1]+nums1[i-2])/2.0;
        }else {
            if(nums1[i]<nums2[j]){
                if(i+1==nums1Size){
                    return (nums1[i]+nums2[j])/2.0;
                }                
                if(nums1[i+1]<nums2[j]){
                    return (nums1[i]+nums1[i+1])/2.0;
                }else{
                    return (nums1[i]+nums2[j])/2.0;
                }
            }else {
                if(j+1==nums2Size){
                    return (nums2[j]+nums1[i])/2.0;
                }                
                if(nums2[j+1]<nums1[i]){
                    return (nums2[j]+nums2[j+1])/2.0;
                }else{
                    return (nums2[j]+nums1[i])/2.0;
                }
            }             
        }
    }
    //return 0;
}

最后

以上就是唠叨诺言为你收集整理的Leetcode笔记10-寻找两个正序数组的中位数的全部内容，希望文章能够帮你解决Leetcode笔记10-寻找两个正序数组的中位数所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。