Hai con trỏ

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ề:

Xem thêm:

Bài 10: Xâu kí tự

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:

Output:

1 2 3 5 5 6 7 8 9

Lờ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 c luôn là phần tử nhỏ nhất chưa được chọn của dãy a và b
Khi phần tử aᵢ được chọn thì phần tử tiếp theo được xét để đưa vào dãy c là aᵢ₊₁
Khi phần tử bᵢ được chọn thì phần tử tiếp theo được xét để đưa vào dãy c là 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ảng a thể hiện cho phần tử nhỏ nhất trong dãy a chưa được chọn
Ta có một con trỏ j ở mảng b thể hiện cho phần tử nhỏ nhất trong dãy b chư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 a và b được đưa vào dãy c
- Nếu như các phần tử của một trong hai dãy a và b đều được đưa vào dãy c (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í i trong dãy a và j trong dãy b
  - 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

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 11

Output:

3 6

Giả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ỏ i và 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í i và j là k thì in ra kết quả và kết thúc quá trình
Nếu tổng hai phần tử ở vị trí i và j nhỏ hơn k thì tăng i lên 1 đơn vị
Nếu tổng hai phần tử ở vị trí i và j lớn hơn k thì giảm j đ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.