¶ Kĩ thuật hai con trỏ
Tác giả: Phan Đình Khôi - Đại học Bách Khoa Đà Nẵng
Reviewer: Nguyễn Khánh
¶ Lời mở đầu
Bài viết này sẽ giúp bạn tìm hiểu thêm về kỹ thuật hai con trỏ. Kỹ thuật này được sử dụng khá phổ biến, giúp chương trình tiết kiệm thời gian và không gian xử lý.
¶ Bài toán 1
Cho hai dãy số nguyên đã được sắp xếp không giảm và lần lượt có và phần tử. Hãy ghép chúng thành dãy được bố trí theo thứ tự không giảm.
Giới hạn: và .
¶ Phân tích
Hãy cùng xem ví dụ sau đây.
Cho trước hai dãy số và được sắp xếp không giảm:
Làm cách nào để có thể ghép chúng thành một dãy số cũng được sắp xếp không giảm ?
Trước tiên, hãy cùng xác định phần tử đầu tiên của dãy .
Vì dãy được bố trí theo thứ tự không giảm, cho nên phần tử đầu tiên của dãy phải là phần tử có giá trị nhỏ nhất trong cả hai dãy và .
Ta có thể so sánh hai phần tử nhỏ nhất của hai dãy , và đưa phần tử có giá trị nhỏ hơn vào vị trí đầu tiên của dãy .
Dãy và đã được sắp xếp không giảm, vì thế hai phần tử nhỏ nhất ở đây chính là hai phần tử ở vị trí đầu tiên ở mỗi dãy ( và ).
Bây giờ, phần tử tiếp theo của dãy sẽ là phần tử nhỏ nhất trong các phần tử chưa được đưa vào dãy .
Dãy và đã được sắp xếp không giảm, vì thế sau khi đưa vào dãy , là phần tử nhỏ nhất chưa được chọn ở dãy và là phần tử nhỏ nhất chưa được chọn ở dãy .
So sánh và , chọn phần tử có giá trị nhỏ hơn và đưa vào dãy .
Sau khi đưa vào dãy , trở thành phần tử nhỏ nhất chưa được chọn ở dãy .
Vẫn như thế, phần tử tiếp theo của dãy sẽ là phần tử nhỏ nhất trong các phần tử chưa được đưa vào dãy .
So sánh và , chọn phần tử có giá trị nhỏ hơn dãy và đưa vào dãy .
Sau khi đưa vào dãy , trở thành phần tử nhỏ nhất chưa được chọn ở dãy .
Ta nhận thấy rằng
- Tại mọi thời điểm, phần tử tiếp theo được đưa vào dãy sẽ là phần tử có giá trị nhỏ nhất trong các phần tử chưa được chọn.
- Bằng cách so sánh phần tử nhỏ nhất chưa được chọn ở dãy và phần tử nhỏ nhất chưa được chọn ở dãy , phần tử nhỏ hơn sẽ được chọn vào dãy .
- Ban đầu, lúc dãy chưa có phần tử nào
- là phần tử nhỏ nhất chưa được chọn trong dãy .
- là phần tử nhỏ nhất chưa được chọn trong dãy .
- Khi đưa phần tử vào dãy thì phần tử nhỏ nhất chưa được chọn trong dãy sẽ là .
- Khi đưa phần tử vào dãy thì phần tử nhỏ nhất chưa được chọn trong dãy sẽ là .
¶ Giải pháp
Dựa vào những phân tích ta có giải pháp sử dụng hai con trỏ như sau:
- Dãy có con trỏ , con trỏ này bắt đầu ở vị trí đầu dãy .
- Con trỏ này được thể hiện như phần tử nhỏ nhất chưa được chọn trong dãy .
- Dãy có con trỏ , con trỏ này bắt đầu ở vị trí đầu dãy .
- Con trỏ này được thể hiện như phần tử nhỏ nhất chưa được chọn trong dãy .
- Ta sẽ lặp lại công việc này, cho đến khi đưa hết các phần tử trong dãy và vào dãy :
- Khi các phần tử trong một dãy nào đó, dãy hoặc dãy , đều đã được đưa vào dãy : đưa lần lượt các phần tử trong dãy còn lại vào dãy .
- Ngược lại:
- So sánh hai phần tử ở hai con trỏ.
- Đưa phần tử có giá trị nhỏ hơn vào dãy , nếu hai phần tử có giá trị như nhau thì chọn một trong hai.
- Tăng vị trí con trỏ ở phần tử được đưa vào lên một đơn vị.
Để hiểu rõ hơn, ta hãy cùng xem qua ví dụ sau đây:
-
Đặt và .
-
Vì nên ta đưa vào mảng và tăng vị trí lên một.
-
Vì nên ta đưa vào mảng và tăng vị trí lên một.
-
Vì nên ta đưa vào mảng và tăng vị trí lên một.
-
Vì nên ta có thể đưa bất kỳ một trong hai phần tử. Ở đây ta đưa phần tử vào và tăng vị trí lên một.
-
Vì nên ta đưa vào mảng và tăng vị trí lên một.
-
Vì nên ta đưa vào mảng và tăng vị trí lên một.
-
Vì nên ta đưa vào mảng và tăng vị trí lên một.
-
Vì nên ta đưa vào mảng và tăng vị trí lên một.
-
Vì tất cả các phần tử trong dãy đều đã được đưa vào dãy nên từ đưa lần lượt các phần tử chưa được chọn trong dãy vào trong dãy
Cài đặt
int i = 1, j = 1;
vector<int> c;
while (i <= n || j <= m){
if (j == m + 1 || (i <= n && a[i] <= b[j]))
c.push_back(a[i++]);
else
c.push_back(b[j++]);
}
for (auto it: c)
cout << it << " ";
Độ phức tạp
Vị trí con trỏ luôn tăng và tăng quá không quá lần, vị trí con trỏ cũng luôn tăng và tăng không quá lần.
Vì thế độ phức tạp của giải pháp là .
¶ Luyện tập
¶ Bài toán 2
Cho một mảng số nguyên có phần tử, mảng này đã được sắp xếp tăng dần. Hãy tìm hai vị trí khác nhau bất kỳ sao cho tổng của hai phần tử ở hai vị trí đó có giá trị là .
Giới hạn: và
¶ Phân tích
Hãy cùng xem ví dụ sau đây.
Cho trước mảng số được sắp xếp tăng dần và :
Làm cách nào để có thể tìm hai vị trí khác nhau mà tổng hai phần tử ở hai vị trí đó có tổng là ?
Trước tiên, ta có một chút nhận xét sau:
- vì dãy tăng dần.
- .
Có thể thấy, tổng của với các phần tử khác trong dãy đều lớn hơn . Vì thế ta không quan tâm đến nữa.
- .
Có thể thấy, tổng của với các phần tử khác trong các phần tử ta quan tâm đều nhỏ hơn . Vì thế ta không quan tâm đến nữa.
- .
Có thể thấy, tổng của với các phần tử khác trong các phần tử ta quan tâm đều lớn hơn . Vì thế ta không quan tâm đến nữa.
Như vậy, tại một thời điểm bất kỳ, những phần tử chúng ta cần quan tâm đến sẽ là các phần tử trong đoạn nào đó.
Ta có một số nhận xét sau:
- Nếu , trong mảng không tồn tại hai vị trí khác nhau mà tổng hai phần tử ở đó có giá trị là .
- Ngược lại:
- Nếu , ta đã tìm được hai vị trí cần tìm ( và ).
- Nếu , không quan tâm đến nữa và các phần tử chúng ta cần quan tâm đó là các phần tử trong đoạn .
- Nếu , không quan tâm đến nữa và các phần tử chúng ta cần quan tâm đó là các phần tử trong đoạn .
¶ Giải pháp
Từ những phân tích vừa rồi ta có giải pháp sử dụng hai con trỏ như sau:
- Một con trỏ được đặt ở đầu mảng , con trỏ còn lại được đặt ở cuối mảng .
- Nếu tổng của hai phần tử ở hai vị trí con trỏ
- Nhỏ hơn : tăng vị trí con trỏ lên một đơn vị.
- Lớn hơn : giảm vị trí con trỏ đi một đơn vị.
- Tiếp tục di chuyển cho đến khi hai con trỏ gặp nhau.
- Khi con trỏ chưa gặp nhau mà tổng ở hai vị trí con trỏ có giá trị là thì ta đã tìm được hai vị trí cần tìm ( và ), kết thúc chương trình.
Để hiểu rõ hơn, ta hãy cùng xem qua một số ví dụ sau đây:
Ví dụ 1: và .
-
Đặt và .
-
Vì nên giảm vị trí đi một đơn vị.
-
Vì nên tăng vị trí lên một đơn vị.
-
Vì nên giảm vị trí đi một đơn vị.
-
Vì nên tăng vị trí lên một đơn vị.
-
Vì nên hai vị trí cần tìm là hai vị trí và .
Ví dụ 2: và .
-
Đặt và .
-
Vì nên giảm vị trí đi một đơn vị.
-
Vì nên tăng vị trí lên một đơn vị.
-
Vì tăng vị trí lên một đơn vị.
-
Vì giảm vị trí đi một đơn vị.
-
Vì giảm vị trí đi một đơn vị.
-
Vì tăng vị trí lên một đơn vị.
-
Vì nên không tìm được hai vị trí cần tìm.
Cài đặt
int i = 1, j = N;
while (i < j) {
if (a[i] + a[j] == x) {
cout << i << " " << j;
return 0;
}
if (a[i] + a[j] < x)
i += 1;
else
j -= 1;
}
cout << "No solution";
Độ phức tạp
Vị trí con trỏ luôn tăng, vị trí con trỏ thì luôn giảm.
Hơn nữa, sự thay đổi vị trí hai con trỏ này sẽ dừng lại khi tổng hai phần tử ở hai vị trí con trỏ có tổng là hay khi vị trí bằng vị trí .
Vì thế, việc thay đổi vị trí hai con trỏ sẽ không quá lần, độ phức tạp của giải pháp là .
¶ Luyện tập
¶ Bài toán 3
Cho dãy số nguyên dương có phần tử. Hãy tìm độ dài đoạn con dài nhất trong dãy sao cho tổng các phần tử trong đoạn này không quá .
Dữ liệu đảm bảo các phần tử trong dãy đều có giá trị không quá .
Giới hạn: , và .
¶ Phân tích
Để dễ dàng phân tích, ta tạm gọi
- là tổng các phần tử trong đoạn .
- Một đoạn con là đoạn con "tốt" nếu
Qua đây, bài toán của chúng ta sẽ là tìm độ dài đoạn con "tốt" dài nhất.
Vì dãy là một dãy số nguyên dương cho nên
- .
- Nếu đoạn con là đoạn con "tốt" thì với mọi , đoạn là đoạn con "tốt".
- Nếu đoạn con không là đoạn con "tốt" thì với mọi , đoạn không là đoạn con "tốt".
Với là một vị trí bất kỳ, nếu như là vị trí nhỏ nhất sao cho đoạn là một đoạn "tốt" thì
- mọi thì đoạn con là một đoạn "tốt".
- mọi thì đoạn con không là một đoạn "tốt".
- đoạn con là một đoạn con "tốt" dài nhất trong các đoạn con "tốt" có vị trí kết thúc tại .
Từ đó, với mỗi từ đến , nếu ta xác định được vị trí , ta có thể biết được độ dài của đoạn con "tốt" dài nhất của dãy .
Hãy cùng nhận xét vị trí của với mỗi từ đến qua ví dụ sau đây:
Cho trước dãy và