Trong ngày hôm nay, chúng ta sẽ cùng nhau đi tìm hiểu về một kỹ thuật được sử dụng phổ biến trong lập trình giúp giảm độ phức tạp của bài toán một cách đáng kể. Hãy cùng tìm hiểu xem kỹ thuật đó là gì nhé!
Để có thể tiếp thu bài học này một cách tốt nhất
Để có thể nắm bắt tốt nội dung của bài học này, các bạn cần có những kiến thức cơ bản về:
- Biến, kiểu dữ liệu, toán tử trong C++
- Câu điều kiện, vòng lặp, hàm trong C++
- Mảng trong C++
- Các kiến thức cần thiết để theo dõi khóa học
Trong bài học ngày hôm nay, chúng ta sẽ cùng nhau tìm hiểu về:
- Ví dụ về sử dụng hai con trỏ
- Nhận biết sử dụng hai con trỏ
Bài toán đặt ra
Cho hai dãy số nguyên a và b có n và m phần tử lần lượt, được sắp xếp không giảm. Ta cần ghép hai dãy trên thành một dãy mới c, sao cho các phần tử trong dãy c vẫn được sắp xếp không giảm.
Ví dụ:
Input:
4
2 5 7 9
5
1 3 5 6 8Output:
1 2 3 5 5 6 7 8 9Lời giải ban đầu
Một cách tiếp cận thông thường là ta sẽ đọc đồng thời cả hai dãy a và b vào cùng một mảng, sau đó sử dụng hàm sort để thu được kết quả.
Tuy nhiên, độ phức tạp của cách làm trên là O((n+m)log (n+m)), do ta cần sắp xếp một mảng có kích thước n+m. Vậy liệu có cách làm nào tối ưu hơn không?
Nhận xét
Hãy cùng phân tích tính chất của dãy c trong ví dụ trên một chút.
Ta có a = 2, 5, 7, 9 và b = 1, 3, 5, 6, 8. Ta thấy, do dãy c là dãy không giảm, các phần tử trong dãy c là của dãy a và b nên phần tử đầu tiên trong dãy c phải là phần tử nhỏ nhất trong dãy a và b.
Mặc khác, dãy a và b cũng được sắp xếp không giảm nên hai phần tử nhỏ nhất trong dãy a và b là a₀ và b₀. Khi này, ta sẽ so sánh a₀ và b₀ rồi thêm phần tử nhỏ hơn vào dãy c.
Tiếp theo, ta sẽ xét phần tử nhỏ nhất trong dãy a và b chưa được thêm vào dãy c. Do b đã được đưa vào dãy c nên ta sẽ so sánh phần tử nhỏ kế tiếp trong dãy b là b₁ với a₀.
Sau đó, ta lại sẽ xét phần tử nhỏ nhất trong dãy a và b chưa được thêm vào dãy c. Do a₀ đã được đưa vào dãy c nên ta sẽ so sánh phần tử nhỏ kế tiếp trong dãy a là a₁ với b₁ và quá trình lặp lại đến khi tất cả các phần tử của hai dãy được đưa vào dãy c.
Từ những gì mình vừa nêu ở trên, ta có thể rút ra một số nhận xét sau:
- Phần tử tiếp theo được đưa vào dãy
cluôn là phần tử nhỏ nhất chưa được chọn của dãyavàb - Khi phần tử
aᵢđược chọn thì phần tử tiếp theo được xét để đưa vào dãyclàaᵢ₊₁ - Khi phần tử
bᵢđược chọn thì phần tử tiếp theo được xét để đưa vào dãyclàbᵢ₊₁ - Hai giá trị ban đầu được xét là
a₀vàb₀
Vậy thì những nhận xét trên sẽ giúp ta giải quyết bài toán này như thế nào?
Lời giải cải tiến
Dựa vào các nhận xét ở trên, ta có thể đưa ra cách làm như sau:
- Ta có một con trỏ
iở mảngathể hiện cho phần tử nhỏ nhất trong dãyachưa được chọn - Ta có một con trỏ
jở mảngbthể hiện cho phần tử nhỏ nhất trong dãybchưa được chọn - Ta sẽ lặp lại tiến trình sau cho đến khi tất cả phần tử hai dãy
avàbđược đưa vào dãyc- Nếu như các phần tử của một trong hai dãy
avàbđều được đưa vào dãyc(i=n hoặc j=m) thì ta đưa tất cả các phần tử của dãy còn lại vào - Nếu không:
- Xét hai phần tử ở vị trí
itrong dãyavàjtrong dãyb - Chọn phần tử nhỏ hơn vào dãy
c, nếu bằng nhau thì chọn bất kì - Tăng con trỏ của mảng có phần tử được đưa vào dãy
c
- Xét hai phần tử ở vị trí
- Nếu như các phần tử của một trong hai dãy
Khi triển khai ý tưởng trên thành code ta có:
#include
using namespace std;
const int MaxN = 1 + 1e5;
int n, m, a[MaxN], b[MaxN];
vector c;
int main(){
freopen("CTDL.inp","r",stdin);
freopen("CTDL.out","w",stdout);
cin >> n;
for(int i = 0 ; i < n ; ++i)
cin >> a[i];
cin >> m;
for(int i = 0 ; i < m ; ++i)
cin >> b[i];
int i = 0, j = 0;
while(i < n && j < m){
if(a[i] < b[j]){
c.push_back(a[i]);
i++;
}
else{
c.push_back(b[j]);
j++;
}
}
while(i < n){
c.push_back(a[i]);
i++;
}
while(j < m){
c.push_back(b[j]);
j++;
}
for(int i : c)
cout << i << " ";
return 0;
} Trong ví dụ trên ta sử dụng hai biến i và j như hai con trỏ trỏ đến hai phần tử, nên kỹ thuật này được gọi là "Hai con trỏ".
Vậy độ phức tạp của thuật toán trên là O(n+m).
Nhận biết sử dụng hai con trỏ
Trên thực tế, không có một hướng dẫn chính xác là khi nào ta nên sử dụng hai con trỏ hay bài toán dạng nào thì sẽ sử dụng hai con trỏ. Những gì mình sắp chia sẻ là từ những kinh nghiệm cá nhân của mình. Nếu các bạn có thêm bất cứ đóng góp gì cho phần này, hãy chia sẻ ở phần bình luận để mọi người cùng tham khảo.
Một bài toán có thể sử dụng hai con trỏ nếu như:
- Ta có hai biến để thể hiện hai phần tử đang xét hoặc một đoạn đang xét
- Sự tăng giảm của các biến là hoàn toàn độc lập với nhau
- Chiều tăng hoặc giảm của hai biến phải là cố định, có nghĩa là nếu biến đó tăng thì sẽ tăng liên tục, nếu giảm thì phải giảm liên tục. Trên thực tế vẫn có một số thuật toán dùng hai con trỏ mà các biến có thể vừa tăng vừa giảm. Tuy nhiên, khi làm như vậy thì các bạn phải có ràng buộc về quãng tăng giảm của biến và đánh giá được thật chính xác về độ phức tạp thời gian.
Ví dụ mở rộng
Để các bạn có thể hiểu hơn về cách sử dụng hai con trỏ, mình sẽ bổ sung ví dụ sau:
Cho một dãy số nguyên gồm n phần tử aᵢ (n≤10⁵, |aᵢ|≤10⁹) được sắp xếp không giảm. Hãy in ra hai vị trí thuộc dãy a sao cho tổng của hai phần tử ở vị trí đó bằng số nguyên k cho trước. Nếu không có hai vị trí nào thỏa mãn in ra "-1 -1".
Ví dụ:
Input:
7 10
1 1 2 4 7 8 11Output:
3 6Giải thích: Phần tử ở vị trí thứ 3 là 2 và phần tử ở vị trí thứ 6 là 8, tổng của chúng là 10
Với những kiến thức về hai con trỏ mà mình đã nêu ở trên, hãy thử tạm ngưng tại đây rồi suy nghĩ để tự tìm cách giải cho bài toán này nhé!
Các bạn đã nghĩ ra lời giải chưa? Hãy cùng xem lời giải của mình sẽ là gì nhé!
Nhận xét
Ta thấy rằng a₆ + a₀ > k mà a₆ > a₅ > a₄ > a₃ > a₂ > a₁ > a₀ do đó a₆ + a₅ > a₆ + a₄ > a₆ + a₃ > a₆ + a₂ > a₆ + a₁ > a₆ + a₀ > k. Có nghĩa là a₆ cộng với bất cứ phần tử nào cũng lớn hơn k. Do vậy, a₆ sẽ không bao giờ là một phần tử được chọn nên ta sẽ không xét a₆ nữa mà sẽ xét a₅.
Lại có a₀ + a₅ < k. Tương tự lập luận bên trên thì k > a₀ + a₅ > a₀ + a₄ > a₀ + a₃ > a₀ + a₂ > a₀ + a₁. Có nghĩa là a₀ cộng với bất cứ phần tử nào cũng nhỏ hơn k. Do vậy, a₀ sẽ không bao giờ là một phần tử được chọn nên ta sẽ không xét a₀ nữa mà sẽ xét a₁.
Từ những nhận xét mình vừa nêu, các bạn đã tìm được lời giải chưa?
Lời giải
Từ các nhận xét trên ta có lời giải sau:
- Ta có hai con trỏ
ivàj,iở đầu mảng vàjở cuối mảng - Ta tiến hành quá trình sau đến khi hai con trỏ gặp nhau, có nghĩa là đến khi
i=j - Nếu tổng hai phần tử ở vị trí
ivàjlàkthì in ra kết quả và kết thúc quá trình - Nếu tổng hai phần tử ở vị trí
ivàjnhỏ hơnkthì tăngilên 1 đơn vị - Nếu tổng hai phần tử ở vị trí
ivàjlớn hơnkthì giảmjđi 1 đơn vị - Khi hai con trỏ gặp nhau có nghĩa là không có hai phần tử nào thỏa mãn và in ra "-1 -1"
Lời giải trên có độ phức tạp là O(n) do ta chỉ cần duyệt hết một lần dãy đã cho.
Code
#include
using namespace std;
const int MaxN = 1 + 1e5;
int n, a[MaxN], k;
int main(){
freopen("CTDL.inp","r",stdin);
freopen("CTDL.out","w",stdout);
cin >> n >> k;
for(int i = 0 ; i < n ; ++i)
cin >> a[i];
int i = 0, j = n - 1;
while(i < j){
if(a[i] + a[j] == k){
// Cộng 1 do chỉ số mảng ta đang dùng là [0, n - 1] thay vì [1, n]
cout << i + 1 << " " << j + 1 << endl;
break;
}
if(a[i] + a[j] < k)
i++;
else
j--;
}
if(i == j)
cout << "-1 -1" << endl;
return 0;
} Độ phức tạp của chương trình trên là O(n) do ta chỉ cần duyệt hết một lần dãy đã cho.
Kết luận
Qua bài này chúng ta đã nắm được về kỹ thuật "Hai con trỏ".
Bài sau chúng ta sẽ tiếp tục tìm hiểu về "Tìm kiếm max, min trên đoạn tịnh tiến".
Cảm ơn các bạn đã theo dõi bài viết. Hãy để lại bình luận hoặc góp ý của mình để phát triển bài viết tốt hơn. Đừng quên "Luyện tập - Thử thách - Không ngại khó".
Thảo luận:
Nếu bạn có bất kỳ khó khăn hay thắc mắc gì về khóa học, đừng ngần ngại đặt câu hỏi trong phần BÌNH LUẬN bên dưới hoặc trong mục HỎI & ĐÁP trên thư viện Howkteam.com để nhận được sự hỗ trợ từ cộng đồng.
