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 $a$ và $b$ lần lượt có $n$ và $m$ phần tử. Hãy ghép chúng thành dãy $c$ được bố trí theo thứ tự không giảm.
Giới hạn: $n, m \leq 10^5$ và $0 \leq a_i, b_i \leq 10^{9}$.
Phân tích
Hãy cùng xem ví dụ sau đây.
Cho trước hai dãy số $a$ và $b$ được sắp xếp không giảm:
$$ a=[1,3,6,8,10] $$
$$ b=[2,6,7,12,14,15] $$
Làm cách nào để có thể ghép chúng thành một dãy số $c$ 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 $c$.
Vì dãy $c$ được bố trí theo thứ tự không giảm, cho nên phần tử đầu tiên của dãy $c$ phải là phần tử có giá trị nhỏ nhất trong cả hai dãy $a$ và $b$.
Ta có thể so sánh hai phần tử nhỏ nhất của hai dãy $a$, $b$ và đưa phần tử có giá trị nhỏ hơn vào vị trí đầu tiên của dãy $c$.
Dãy $a$ và $b$ đã đượ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 [$a[1]$ và $b[1]$].
$$ a=[\overset{\downarrow}{\color{red}1},3,6,8,10] $$
$$ b=[\overset{\downarrow}{2},6,7,12,14,15] $$
$$ c=[{\color{red}1}] $$
Bây giờ, phần tử tiếp theo của dãy $c$ sẽ là phần tử nhỏ nhất trong các phần tử chưa được đưa vào dãy $c$.
Dãy $a$ và $b$ đã được sắp xếp không giảm, vì thế sau khi đưa $a[1]$ vào dãy $c$, $a[2]$ là phần tử nhỏ nhất chưa được chọn ở dãy $a$ và $b[1]$ là phần tử nhỏ nhất chưa được chọn ở dãy $b$.
So sánh $a[2]$ và $b[1]$, chọn phần tử có giá trị nhỏ hơn và đưa vào dãy $c$.
$$ a=[1,\overset{\downarrow}{3},6,8,10] $$
$$ b=[\overset{\downarrow}{\color{red}2},6,7,12,14,15] $$
$$ c=[1,{\color{red}2}] $$
Sau khi đưa $b[1]$ vào dãy $c$, $b[2]$ trở thành phần tử nhỏ nhất chưa được chọn ở dãy $b$.
Vẫn như thế, phần tử tiếp theo của dãy $c$ sẽ là phần tử nhỏ nhất trong các phần tử chưa được đưa vào dãy $c$.
So sánh $b[2]$ và $a[2]$, chọn phần tử có giá trị nhỏ hơn dãy và đưa vào dãy $c$.
$$ a=[1,\overset{\downarrow}{\color{red}3},6,8,10] $$
$$ b=[2,\overset{\downarrow}{6},7,12,14,15] $$
$$ c=[1,2,{\color{red}3}] $$
Sau khi đưa $a[2]$ vào dãy $c$, $a[3]$ trở thành phần tử nhỏ nhất chưa được chọn ở dãy $a$.
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 $c$ 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 $a$ và phần tử nhỏ nhất chưa được chọn ở dãy $b$, phần tử nhỏ hơn sẽ được chọn vào dãy $c$.
- Ban đầu, lúc dãy $c$ chưa có phần tử nào
- $a[1]$ là phần tử nhỏ nhất chưa được chọn trong dãy $a$.
- $b[1]$ là phần tử nhỏ nhất chưa được chọn trong dãy $b$.
- Khi đưa phần tử $a[i]$ vào dãy $c$ thì phần tử nhỏ nhất chưa được chọn trong dãy $a$ sẽ là $a[i+1]$.
- Khi đưa phần tử $b[j]$ vào dãy $c$ thì phần tử nhỏ nhất chưa được chọn trong dãy $b$ sẽ là $b[j+1]$.
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 $a$ có con trỏ $i$, con trỏ này bắt đầu ở vị trí đầu dãy $a$.
- Con trỏ $i$ này được thể hiện như phần tử nhỏ nhất chưa được chọn trong dãy $a$.
- Dãy $b$ có con trỏ $j$, con trỏ này bắt đầu ở vị trí đầu dãy $b$.
- Con trỏ $j$ này được thể hiện như phần tử nhỏ nhất chưa được chọn trong dãy $b$.
- 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 $a$ và $b$ vào dãy $c$:
- Khi các phần tử trong một dãy nào đó, dãy $a$ hoặc dãy $b$, đều đã được đưa vào dãy $c$: đưa lần lượt các phần tử trong dãy còn lại vào dãy $c$.
- 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 $c$, 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:
$a = [1, 3, 6, 8, 10], b = [2, 6, 7, 12, 14,15]$
- Đặt $i = 1$ và $j = 1$. $a = [\overset{\underset{\downarrow}{\color{red}i}}{\color{red}1}, 3, 6, 8, 10]$ $b = [\underset{\overset{\uparrow}{\color{blue}j}}{\color{blue}2}, 6, 7, 12, 14,15]$ $c = []$
- Vì $a[i]