- Thẻ: Mảng, Con trỏ kép, Sắp xếp
- Độ khó: Dễ
Tóm tắt bài toán
Mô tả: Cho hai mảng đã sắp xếp nums1 và nums2.
Yêu cầu: Gộp mảng nums2 vào mảng nums1 sao cho nums1 trở thành một mảng đã sắp xếp.
Chú ý:
- Mảng nums1 có kích thước m+n, trong đó m phần tử đầu tiên là các phần tử của mảng nums1. Mảng nums2 có kích thước n.
- nums1.length==m+n.
- nums2.length==n.
- 0≤m,n≤200.
- 1≤m+n≤200.
- −109≤nums1[i],nums2[j]≤109.
Ví dụ:
Ý tưởng giải quyết
Ý tưởng 1: Con trỏ nhanh và chậm
- Sử dụng hai con trỏ index1 và index2 để trỏ vào cuối mảng nums1 và nums2, và sử dụng một con trỏ index để trỏ vào cuối mảng nums1.
- Từ cuối mảng, so sánh giá trị hiện tại của nums1[index1] và nums2[index2], lưu giá trị lớn hơn vào nums1[index], sau đó tiếp tục duyệt về phía trước.
- Cuối cùng, gán các phần tử còn lại trong mảng nums2 vào vị trí tương ứng trong mảng nums1.
Ý tưởng 1: Code
Ý tưởng 1: Phân tích độ phức tạp
- Độ phức tạp thời gian: O(m+n).
- Độ phức tạp không gian: O(m+n).