Coding interview練習 合併排序數字陣列

合併兩個有排序的數字陣列。

題目

A:Merge two given sorted number arrays, the result will be one sorted array.

e.g.
  input: [1, 2, 3], [5, 6]
  output: [1, 2, 3, 5, 6]

  input: [3, 5], [2, 3, 8, 9]
  output: [2, 3, 3, 5, 8, 9]

提問

Q:數字陣列是否含浮點數、負數？
A:假設只有整數。

Q:陣列可能為空嗎？
A:陣列不為空。

Q:陣列元素會重複嗎？例如[1, 2, 2, 3]。
A:可能會重複。

Q:有記憶體限制嗎？
A:假設沒記憶體限制。

先想到的解法

直覺就是先合併兩個陣列然後排序，至於排序就交給函式庫，除非提問是實作排序否則排序直接用函式庫即可。Arrays.sort(Object[] a)時間複雜度為O(n log(n))，排序兩陣列合併的陣列為O(n+m)，空間複雜度需要合併兩陣列的新鎮列為O(n+m)。

Main.java

package com.abc.demo;

import java.util.Arrays;

public class Main {

    public static void main(String[] arges) {
        System.out.println(Arrays.toString(mergeSortedArray(new int[]{2, 3, 8}, new int[]{3, 5})));
        System.out.println(Arrays.toString(mergeSortedArray(new int[]{1, 3, 4}, new int[]{5, 6})));
        System.out.println(Arrays.toString(mergeSortedArray(new int[]{6}, new int[]{1, 2, 3})));
        System.out.println(Arrays.toString(mergeSortedArray(new int[]{-1, 0, 9, 10}, new int[]{-2, 9})));
    }

    public static int[] mergeSortedArray(int[] arr1, int[] arr2) {
        int[] mergedArr = new int[arr1.length + arr2.length]; // 建立一個新陣列，長度為兩陣列的和
        for (int i = 0; i < arr1.length; i++) { // 迴圈把陣列一放到新陣列 tc:O(n)
            mergedArr[i] = arr1[i];
        }
        for (int j = 0; j < arr2.length; j++) { // 迴圈把陣列二放到新陣列，從陣列一的後面開始放 tc:O(m)
            mergedArr[arr1.length + j] = arr2[j];
        }
        Arrays.sort(mergedArr); // O(n log(n)) // 排序，O(log(n + m))
        return mergedArr;
    }
}

更加解

跑一個迴圈可同時遍歷兩個陣列，從兩陣列開始的元素比較，若陣列一的數小於陣列二的數則將陣列一的數放入，反之放入陣列二的數，最後需要一個判斷把陣列一大於陣列二最大的數放入新陣列。

arr1=[2,3,8], arr2=[3,5], mergedArr=[0,0,0,0,0]
L1=========================================================
        v (i=0)
  arr1=[2,3,8]
        v (j=0)
  arr2=[3,5]

  mergedArr=[2,0,0,0,0] (k=1)
          v (i=1)
  arr1=[2,3,8]

L2=========================================================
          v (i=1)
  arr1=[2,3,8]
        v (j=0)
  arr2=[3,5]

  mergedArr=[2,3,0,0,0] (k=2)
          v (j=1)
  arr2=[3,5]

L3=========================================================
          v (i=1)
  arr1=[2,3,8]
          v (j=1)
  arr2=[3,5]

  mergedArr=[2,3,3,0,0] (k=3)
            v (i=2)
  arr1=[2,3,8]

L4=========================================================
            v (i=2)
  arr1=[2,3,8]
          v (j=1)
  arr2=[3,5]

  mergedArr=[2,3,3,5,0] (k=4)
            v (j=2)
  arr2=[3,5]

L5=========================================================
            v (i=2)
  arr1=[2,3,8]
            v (j=2)
  arr2=[3,5]

  mergedArr=[2,3,3,5,8] (k=5)
              v (i=3)
  arr1=[2,3,8]

Main.java

package com.abc.demo;

import java.util.Arrays;

public class Main {

    public static void main(String[] arges) {
        System.out.println(Arrays.toString(mergeSortedArray(new int[]{2, 3, 8}, new int[]{3, 5})));
        System.out.println(Arrays.toString(mergeSortedArray(new int[]{1, 3, 4}, new int[]{5, 6})));
        System.out.println(Arrays.toString(mergeSortedArray(new int[]{6}, new int[]{1, 2, 3})));
        System.out.println(Arrays.toString(mergeSortedArray(new int[]{-1, 0, 9, 10}, new int[]{-2, 9})));
    }

    public static int[] mergeSortedArray(int[] arr1, int[] arr2) {
        int[] mergedArr = new int[arr1.length + arr2.length]; // 建立一個新陣列，長度為兩陣列的和
        int i = 0; // 遍歷陣列一的索引
        int j = 0; // 遍歷陣列二的索引
        int k = 0; // 目前合併陣列已裝填的數目
        while (k < mergedArr.length) { // 新陣列未裝滿前持續迴圈 tc:O(n+m)
            if ((i < arr1.length && j < arr2.length) && arr1[i] < arr2[j]) { // 當陣列一的值小於陣列二且索引都未超過長度時將陣列一的值放入新陣列
                mergedArr[k] = arr1[i];
                i++; // 推進陣列一的索引
            } else if (j < arr2.length) { // 反之把陣列二的值放入新陣列
                mergedArr[k] = arr2[j];
                j++; // 推進陣列二的索引
            } else if (i < arr1.length) { // 當陣列一的數大於陣列二的最大數時，將陣列一的數放入新陣列，
                mergedArr[k] = arr1[i];
                i++; // 推進陣列一的索引
            }
            k++; // 遞增新陣列已裝填的數目
        }

        return mergedArr;
    }
}

雖然思路方向正確，但把步驟轉換成程式時一直卡在怎麼同時遍歷兩個陣列，一開始都用兩個for迴圈去做的方式錯誤，最後看了參考才知道能用while迴圈和多個索引即可在一次廽圈中遍歷多個陣列。此外還是需要靠試誤和debugger去處理溢位的問題及一些想法上的疏漏。