Mô tả

https://leetcode.com/problems/merge-sorted-array/

Ý tưởng

• Sử dụng hai con trỏ để duyệt từ cuối mảng nums1 (vị trí m-1) và nums2 (vị trí n-1).

• Bắt đầu điền giá trị vào vị trí cuối cùng của nums1 (tại m + n - 1), và so sánh giá trị từ hai mảng:

  • Nếu n == 0: Mảng nums2 đã được ghép xong → Dừng thuật toán.

  • Nếu m == 0: Chỉ còn lại các phần tử trong nums2, ta sao chép toàn bộ vào đầu nums1.

  • Nếu nums1[m - 1] > nums2[n - 1]: Đưa nums1[m - 1] vào vị trí cuối cùng, sau đó giảm m.

  • Ngược lại: Đưa nums2[n - 1] vào vị trí cuối cùng, sau đó giảm n.

👉 Quá trình này tiếp tục cho đến khi tất cả phần tử của nums2 được ghép vào nums1.

My solution

https://leetcode.com/problems/merge-sorted-array/solutions/6458322/solution-with-two-pointer/

Code

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        while (m + n - 1 >= 0) {
            if (n == 0) {
                break;
            } else if (m == 0) {
                nums1[n - 1] = nums2[n - 1];
                n--;
            } else if (nums1[m - 1] > nums2[n - 1]) {
                nums1[m + n - 1] = nums1[m - 1];
                m--;
            } else {
                nums1[m + n - 1] = nums2[n - 1];
                n--;
            }
        }
    }
}

Độ phức tạp

• Time complextity: O(n)

• Space complexity: O(1)