程式小試身手

朋友很力挺繼續練習程式邏輯,讓我加入讀書會! 看到Google 2020年考古題，網路上很多好人們分享的  https://leetcode.com/list/5sc699lg

決定慢慢來破解它

第一個想法 是 A + B → 排序 → 取中位數 但顯然這不符合題意 O(log(m+n)) 正解: 點擊此處

時間複雜度複習:初學者學演算法-談什麼是演算法和時間複雜度

---------------------------------------------

第二次挑戰

因為閱讀上面文章後，開始覺得應該是先用合併排序法，結果遇到int/2結果是錯誤的，下次需要特別記得為double [] merge_ary

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
     int left_index=0;
     int right_index=0;
     int merge_index=0;
     double [] merge_ary=new double[nums1.length+nums2.length];
        while (left_index<nums1.length && right_index<nums2.length){
            if(nums1[left_index]<nums2[right_index]){
                merge_ary[merge_index]=nums1[left_index];
                merge_index++;
                left_index++;
            }else{
                merge_ary[merge_index]=nums2[right_index];
                merge_index++;
                right_index++;
            }
        }
            while(left_index<nums1.length){
                merge_ary[merge_index]=nums1[left_index];
                 merge_index++;
                left_index++;
            }
             while(right_index<nums2.length){
                merge_ary[merge_index]=nums2[right_index];
                merge_index++;
                right_index++;
            }
         if(merge_ary.length%2==0){
           //偶數
           int middle = merge_ary.length/2;//EX.4/2=2
             System.out.print("middle="+middle+","+(merge_ary[middle-1]+merge_ary[middle])/2);
           return (merge_ary[middle-1]+merge_ary[middle])/2;
       }else{
           //奇數
           int middle = merge_ary.length/2;//EX.3/2=1.5
            return merge_ary[middle];
       }
        
    }
}

第一次挑戰之紀錄

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        //array相加並排序
        int [] newNums = new int[nums2.length+nums1.length];
        for(int j=0;j<nums1.length;j++){
            newNums[j]=nums1[j];
        }
        for(int i=0;i<nums2.length;i++){
            newNums[nums1.length+i]=nums2[i];
        }
        Arrays.sort(newNums);//-->此處偷懶,但我想可以用泡泡排序
        //長度除以2餘數為1有中間值,除出的值為index,餘數為0則中間左右除以2,除出的值為index-1
        int answer=0;
        if((newNums.length%2)==1){
            int index=newNums.length/2;
            answer=newNums[index];
        }
        if((newNums.length%2)==0){
            int index=newNums.length/2;
            answer=newNums[index-1];
        }
        return answer;
    }
}