Hai con trỏ

Dẫn nhập

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 khá phổ biến trong lập trình giúp giảm độ phức tạp của bài toán đi rất nhiều. Hãy cùng tìm hiểu xem kỹ thuật đó là gì nhé!

Nội dung

Để có thể tiếp thu bài học này một cách tốt nhất, các bạn nê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  và  lần lượt gồm n và m phần tử được sắp xếp không giảm . Hãy ghép hai dãy trên thành một dãy mới  sao cho các phần tử trong dãy  được sắp xếp không giảm

Ví dụ:

Lời giải ban đầu

Theo một suy nghĩ thông thường, ta sẽ đọc đồng thời cả hai dãy  và  vào cùng một mảng sau đó dùng hàm sort để thu được kết quả.

Từ suy nghĩ trên, ta có thể triển khai code như sau:

#include<bits/stdc++.h>
using namespace std;

const int MaxN = 1 + 1e5;

int n, m, c[MaxN];

int main(){
    freopen("CTDL.inp","r",stdin);
    freopen("CTDL.out","w",stdout);
    cin >> n;
    for(int i = 0 ; i < n ; ++i) cin >> c[i];
    cin >> m;
    for(int i = 0 ; i < m ; ++i) cin >> c[n + i];
    sort(c, c + n + m);
    for(int i = 0 ; i < n + m ; ++i) cout << c[i] << " ";

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

Tuy nhiên, độ phức tạp của chương trình trên sẽ là  do ta cần sort một mảng có kích thước . 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  trong ví dụ trên một chút.

Ta có

Ta thấy, do dãy  là dãy không giảm, các phần tử trong dãy  là của dãy  và  nên phần tử đầu tiên trong dãy  phải là phần tử nhỏ nhất trong dãy  và .

Mặc khác, dãy  và  cũng được sắp xếp không giảm nên hai phần tử nhỏ nhất trong dãy  và  là  và . Khi này, ta sẽ so sánh  và  rồi thêm phần tử nhỏ hơn vào dãy .

Tiếp theo, ta sẽ xét phần tử nhỏ nhất trong dãy  và  chưa được thêm vào dãy . Do  đã được đưa vào dãy  nên ta sẽ so sánh phần tử nhỏ kế tiếp trong dãy  là  với .

Sau đó, ta lại sẽ xét phần tử nhỏ nhất trong dãy  và  chưa được thêm vào dãy . Do  đã được đưa vào dãy  nên ta sẽ so sánh phần tử nhỏ kế tiếp trong dãy  là  với  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

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  luôn là phần tử nhỏ nhất chưa được chọn của dãy  và 
• Khi phần tử  được chọn thì phần tử tiếp theo được xét để đưa vào dãy  là 
• Khi phần tử  được chọn thì phần tử tiếp theo được xét để đưa vào dãy  là 
• Hai giá trị ban đầu được xét là  và 

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ỏ  ở mảng  thể hiện cho phần tử nhỏ nhất trong dãy  chưa được chọn
• Ta có một con trỏ  ở mảng  thể hiện cho phần tử nhỏ nhất trong dãy  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  và  được đưa vào dãy 
  • Nếu như các phần tử của một trong hai dãy  và  đều được đưa vào dãy   hoặc  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í  trong dãy  và  trong dãy 
    • Chọn phần tử nhỏ hơn vào dãy , 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 

Khi triển khai ý tưởng trên ra code ta có

#include<bits/stdc++.h>
using namespace std;

const int MaxN = 1 + 1e5;

int n, m, a[MaxN], b[MaxN];
vector<int> 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(i == n){
            c.push_back(b[j]);
            j++;
            continue;
        }
        if(j == m){
            c.push_back(a[i]);
            i++;
            continue;
        }
        if(a[i] < b[j]){
            c.push_back(a[i]);
            i++;
        }
        else {
            c.push_back(b[j]);
            j++;
        }
    }
    for(int i : c) cout << i << " ";

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

Trong ví dụ trên ta sử dụng hai biến  và  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à bao nhiêu? Ta thấy vòng lặp while lặp lại  lần, mỗi thao tác trong vòng lặp là  nên độ phức tạp của chương trình sẽ chỉ là .

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 cho 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  phần tử  được sắp xếp không giảm. Hãy in ra hai vị trí thuộc dãy  sao cho tổng của hai phần tử ở vị trí đó bằng số nguyên  cho trước. Nếu không có hai vị trí nào thỏa mãn in ra “-1 -1”.

Ví dụ:

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  mà  do đó . Có nghĩa là  cộng với bất cứ phần tử nào cũng lớn hơn . Do vậy,  sẽ không bao giờ là một phần tử được chọn nên ta sẽ không xét  nữa mà sẽ xét .

Lại có . Tương tự lập luận bên trên thì . Có nghĩa là  cộng với bất cứ phần tử nào cũng nhỏ hơn . Do vậy,  sẽ không bao giờ là một phần tử được chọn nên ta sẽ không xét  nữa mà sẽ xét .

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ỏ  và ,  ở đầu mảng và  ở 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 

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

Code

#include<bits/stdc++.h>
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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

Độ phức tạp của chương trình trên là 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ề 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ó”.

---

Tải xuống

Tài liệu

Nhằm phục vụ mục đích học tập Offline của cộng đồng, Kteam hỗ trợ tính năng lưu trữ nội dung bài học Hai con trỏ dưới dạng file PDF trong link bên dưới.

Ngoài ra, bạn cũng có thể tìm thấy các tài liệu được đóng góp từ cộng đồng ở mục TÀI LIỆU trên thư viện Howkteam.com

Đừng quên like và share để ủng hộ Kteam và tác giả nhé!

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.

CỘNG ĐỒNG HỎI ĐÁP HOWKTEAM.COM

GROUP THẢO LUẬN FACEBOOK