88. Merge Sorted Array

Problem

Bài toán yêu cầu bạn trộn hai mảng đã được sắp xếp (nums1 và nums2) thành một m ảng duy nhất được sắp xếp theo thứ tự không giảm, và kết quả phải được lưu trực tiếp vào mảng nums1. nums1 có đủ chỗ để chứa toàn bộ phần tử của cả hai mảng (có m phần tử thực sự và n phần tử 0 ở cuối để chứa thêm n phần tử từ nums2)

Approach

Sử dụng ba pointer

i: Trỏ vào phần tử cuối cùng của phần hợp lệ, trong nums1 (i = m - 1)

j: Trỏ vào phần tử cuối cùng của nums2 (j = n - 1)

k: Trỏ vào vị trí cuối cùng của nums1 (k =m + n - 1)

So sánh nums1[i] và nums2[j], đặt phần tử lớn hơn vào nums1[k], sau đó giảm pointer tương ứng

Lặp lại cho đến khi đã duyệt hết nums2 (j < 0), nếu nums1 còn phần tử thì chúng đã ở đúng vị trí, không cần xử lý thêm

💡

Ưu điểm của cách làm này là không cần dùng mảng phụ, mọi thao tác đều diễn ra trực tiếp trên nums1 từ cuối về đầu nên không bị ghi đè dữ liệu

Time and space complexity

TC: O(m + n)

SC: O(1)

Solution

typescripttypescript

1/**
2 Do not return anything, modify nums1 in-place instead.
3 */
4function merge(nums1: number[], m: number, nums2: number[], n: number): void {
5    let i = m - 1;
6    let j = n - 1;
7    let k = m + n - 1;
8
9    while (j >= 0) {
10        if (i >= 0 && nums1[i] > nums2[j]) {
11            nums1[k] = nums1[i];
12            i--
13        } else {
14            nums1[k] = nums2[j];
15            j--
16        }
17        k--
18    }
19};

💡

Giải thích ngắn gọn

Duyệt từ cuối mảng về đầu để tránh ghi đè

So sánh và chèn phần tử lớn hơn và cuối nums1

Không cần dùng mảng phụ, thao tác in-place

💡

nums1 có bị mất item khi đang thực hiện function không?

nums1 ban đầu gồm m phần tử hợp lệ (đã được sắp xếp) và n số 0 ở cuối để dành cho chỗ n phần tử từ nums2

Thuật toán luôn điền từ cuối mảng nums1 về đầu (từ vị trí k = m + n - 1 về 0), nên các phần tử gốc của nums1 sẽ không bị ghi đè trước khi chúng được xử lý

Khi so sánh, nếu phần tử ở nums1 lớn hơn, nó sẽ được dời xuống vị trí cuối, sau đó con trỏ i giảm đi, tiếp tục xét phần tử trước đó

Nếu phần tử ở nums2 lớn hơn, nó sẽ được chèn vào cuối, con trỏ j giảm đi

Không có trường hợp nào các số hợp lệ ban đầu của nums1 bị ghi đề trước khi được xử lý

Loading content...

1/** 2 Do not return anything, modify nums1 in-place instead. 3 */ 4function merge(nums1: number[], m: number, nums2: number[], n: number): void { 5 let i = m - 1; 6 let j = n - 1; 7 let k = m + n - 1; 8 9 while (j >= 0) { 10 if (i >= 0 && nums1[i] > nums2[j]) { 11 nums1[k] = nums1[i]; 12 i-- 13 } else { 14 nums1[k] = nums2[j]; 15 j-- 16 } 17 k-- 18 } 19};

88. Merge Sorted Array

Related Posts

Related Posts

88. Merge Sorted Array

Related Posts

2. Add Two Numbers

3. Longest Substring Without Repeating Characters

3. Longest Substring Without Repeating Characters

4. Median of Two Sorted Arrays

5. Longest Palindromic Substring

6. Zigzag Conversion

9. Palindrome Number

11. Container With Most Water

12. Integer to Roman

13. Roman to Integer

14. Longest Common Prefix

17. Letter Combinations of a Phone Number

19. Remove Nth Node From End of List

20. Valid Parentheses

21. Merge Two Sorted Lists

Related Posts

2. Add Two Numbers

3. Longest Substring Without Repeating Characters

3. Longest Substring Without Repeating Characters

4. Median of Two Sorted Arrays

5. Longest Palindromic Substring

6. Zigzag Conversion

9. Palindrome Number

11. Container With Most Water

12. Integer to Roman

13. Roman to Integer

14. Longest Common Prefix

17. Letter Combinations of a Phone Number

19. Remove Nth Node From End of List

20. Valid Parentheses

21. Merge Two Sorted Lists