88. Merge Sorted Array - Easy

前往題目

想法

• 雙指針

思路

只要把nums1真正的數字們複製到一個新的陣列就很好操作了，這個操作時間只要+m次

1. 把nums1真正的數字複製到新的陣列
2. 三個指針分別指向:新的nums1陣列、原nums1、nums2
3. 疊代原先的nums1陣列
4. 每次用雙指針比較數字，並放入nums1

不難的題目，但是寫條件的時候要小心

Code

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int[] nums1Elements = new int[m]; // real element of nums1

        // Get the nums1 elements
        for (int i = 0; i < m; ++i) {
            nums1Elements[i] = nums1[i];
        }

        int nums1ElementsIndex = 0; 
        int nums1Index = 0;
        int nums2Index = 0;

        while (nums1Index < nums1.length) {

            // When nums1 exhausted but nums2 hasn't
            if (nums1ElementsIndex >= m && nums2Index < n) {
                nums1[nums1Index] = nums2[nums2Index];
                ++nums2Index;
            } else if (nums2Index >= n && nums1ElementsIndex < m) {  // When nums2 exhausted but nums2 hasn't
                nums1[nums1Index] = nums1Elements[nums1ElementsIndex];
                ++nums1ElementsIndex;
            } else if (nums1Elements[nums1ElementsIndex] > nums2[nums2Index]) { // Current nums1 element is larger than nums2 element
                nums1[nums1Index] = nums2[nums2Index];
                ++nums2Index;
            } else if (nums1Elements[nums1ElementsIndex] < nums2[nums2Index]) { // Current nums2 element is larger than nums2 element
                nums1[nums1Index] = nums1Elements[nums1ElementsIndex];
                ++nums1ElementsIndex;
            } else { // Equal
                nums1[nums1Index] = nums1Elements[nums1ElementsIndex];
                ++nums1ElementsIndex;
            }

            ++nums1Index;
        }
        return;
    }
}