4. Median of Two Sorted Arrays

这道题最简单的思路是把两个数组合并起来,再排序,如果数组长度是奇数,return 中间的那个数,如果数组长度是偶数,return 中间两个数的平均值。时间复杂度 O(nlogn)用于数组排序。

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int[] nums = new int[nums1.length+nums2.length];
        int i=0;
        for(;i<nums1.length;i++){
            nums[i]=nums1[i];
        }
        for(int j=0;j<nums2.length;j++){
            int n = nums.length;
            nums[i+j]=nums2[j];
        }
        Arrays.sort(nums);
        int rest = nums.length%2;
        int index = nums.length/2;
        if(rest==1){
            return nums[index];
        }
        else{
            return ((double)(nums[index-1]+nums[index])/2);
        }
    }

但是这道题的题目要求:The overall run time complexity should be O(log (m+n)),这两个数组是有序数组,看来不需要combine两个数组再排序。

上一篇:模块的多级导入,或者叫嵌套的处理。如何避免修改模块


下一篇:苹果编程语言Swift简介