Dương Âm Xen Kẽ

Nguồn: Đề thi Cử nhân tài năng (CTDL & GT) – Câu 3 Độ khó: Trung bình Hai con trỏ Mảng Tư duy

Đề bài

Câu 3 (4 điểm)

Cho mảng một chiều $a$ chứa $n$ phần tử gồm cả số nguyên dương lẫn nguyên âm. Viết hàm (cùng các hàm phụ trợ, nếu cần thiết) để hoán đổi các con số sao cho dương và âm xen kẽ nhau. Những số dương (hay âm) còn lại (nếu có) sẽ bị đẩy về cuối mảng.

Ví dụ: Mảng có 10 số

Nhập	Xuất
8 -8 -7 -9 3 3 2 -2 -7 10	3 -8 2 -9 3 -7 8 -2 10 -7
-7 -9 -6 10 5 -7 -5 -10 8 4	5 -9 10 -10 8 -7 4 -6 -5 -7
-3 -1 4 8 -8 1 1 5 10 8	8 -1 4 -3 1 -8 1 5 10 8

Yêu cầu: Hàm thực thi với chi phí $\Theta(n)$ và không sử dụng thêm mảng phụ.

Mẫu của hàm như sau:

void Cau3(int a[], int n);

Để chạy thử như một chương trình

Đề chỉ yêu cầu viết hàm. Để các bạn chạy thử, trong bài này chương trình đọc dòng đầu là $n$, dòng sau là $n$ số của mảng, gọi Cau3(a, n) rồi in mảng kết quả. Xem ví dụ của đề thì mảng luôn bắt đầu bằng số dương: dương, âm, dương, âm…

Ví dụ 1 – input

10
8 -8 -7 -9 3 3 2 -2 -7 10

Ví dụ 1 – một output đúng

3 -8 2 -9 3 -7 8 -2 10 -7

Lời mở đầu

Bài này là câu 3 trong một đề thi Cử nhân tài năng môn Cấu trúc dữ liệu & Giải thuật, được một bạn học viên nhắn tin hỏi mình. Phải công nhận đề Cử nhân tài năng hay mà độ khó cũng khá tốt nha các bạn 😄. Mình tổng hợp lại cuộc trò chuyện đó thành bài giải chi tiết để nhiều bạn được tham khảo luôn. Hy vọng mang đến được giá trị cho các bạn 😇.

Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì link bài đây nhé:

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Mình giải thích lại đề cho bạn nào chưa rõ: mảng có cả số dương và số âm, ta phải đổi chỗ các số sao cho mảng có dạng dương, âm, dương, âm, …. Nếu số dương nhiều hơn số âm thì sau khi xen kẽ hết, các số dương dư ra nằm dồn ở cuối mảng; ngược lại thì các số âm dư nằm ở cuối.

Ví dụ 3: mảng -3 -1 4 8 -8 1 1 5 10 8 có 7 số dương và 3 số âm. Ta xen kẽ được 3 cặp 8 -1 4 -3 1 -8, còn dư 4 số dương 1 5 10 8 nằm ở cuối.

Đáp án không duy nhất

Đề không yêu cầu giữ thứ tự các số, nên có rất nhiều cách xếp đúng. Cột "Xuất" của đề chỉ là một cách xếp đúng; code của các bạn in ra thứ tự khác vẫn đúng, miễn là: (1) vẫn đủ các số của mảng ban đầu, (2) $2m$ vị trí đầu ($m$ = min(số dương, số âm)) xen kẽ dương – âm bắt đầu bằng dương, (3) phần còn lại cùng một dấu.

Cái khó của bài nằm ở dòng yêu cầu cuối: chạy trong $\Theta(n)$ và không dùng mảng phụ. Nếu được dùng mảng phụ thì bài này dễ ợt, nên mình sẽ đi từ cách dễ trước rồi tới cách đúng yêu cầu.

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Cách 1Tách 2 mảng phụ rồi trộn · O(N) nhưng tốn mảng phụCách 2Hai con trỏ, đổi chỗ tại chỗ · O(N), O(1) bộ nhớ

Cách 1Tách ra 2 mảng phụ rồi trộn xen kẽ – O(N)

Cách đơn giản nhất ai cũng nghĩ ra: duyệt mảng, số dương bỏ vào mảng duong, số âm bỏ vào mảng am. Sau đó ghi ngược lại vào a: lấy 1 số dương, rồi 1 số âm, rồi 1 số dương… mảng nào hết trước thì cứ lấy tiếp mảng còn lại, tự nhiên phần dư sẽ nằm ở cuối.

Source code để các bạn tham khảo nếu làm theo hướng này:

#include <iostream>
#include <vector>
using namespace std;

void Cau3(int a[], int n){
    vector<int> duong, am;
    for(int i = 0; i < n; ++i){
        if(a[i] > 0){
            duong.push_back(a[i]);
        }
        else{
            am.push_back(a[i]);
        }
    }
    int k = 0, x = 0, y = 0;
    while(x < (int)duong.size() || y < (int)am.size()){
        if(x < (int)duong.size()){
            a[k++] = duong[x++];
        }
        if(y < (int)am.size()){
            a[k++] = am[y++];
        }
    }
}

int main(){
    int n;
    cin >> n;
    int *a = new int[n];
    for(int i = 0; i < n; ++i){
        cin >> a[i];
    }
    Cau3(a, n);
    for(int i = 0; i < n; ++i){
        cout << a[i] << " ";
    }
    delete[] a;
    return 0;
}

def Cau3(a, n):
    duong = [x for x in a if x > 0]
    am = [x for x in a if x <= 0]
    k = x = y = 0
    while x < len(duong) or y < len(am):
        if x < len(duong):
            a[k] = duong[x]; k += 1; x += 1
        if y < len(am):
            a[k] = am[y]; k += 1; y += 1


n = int(input())
a = list(map(int, input().split()))
Cau3(a, n)
print(*a)

Không gian$O(N)$ (mảng phụ)

Thời gian$O(N)$

Không đạt yêu cầu đề

Cách này chạy $O(N)$ nhưng dùng 2 mảng phụ duong, am, vi phạm yêu cầu "không sử dụng thêm mảng phụ" nên đi thi sẽ không được trọn điểm. Tuy vậy nó rất dễ cài và chắc chắn đúng, nên mình dùng nó làm code đối chiếu khi kiểm tra cách 2.

Cách 2Hai con trỏ, đổi chỗ ngay trên mảng – O(N), không mảng phụ

Bài này mình chia làm 2 bước, và cả 2 bước đều là ứng dụng hai con trỏ.

Bước 1: Dồn hết số dương về đầu, số âm về cuối

Đầu tiên hãy đưa hết các phần tử dương về đầu mảng, âm về cuối mảng; thứ tự trong mỗi nhóm ra sao không quan trọng. Ví dụ 8, -8, -7, -9, 3, 3, 2, -2, -7, 10 ta có thể được 8, 3, 3, 2, 10, -8, -7, -9, -2, -7, miễn là dương gom hết về đầu, âm gom hết về cuối. Làm như sau:

• Đặt L = 0, R = n - 1, tức L là index đầu, R là index cuối mảng. Điều kiện lặp: L < R.
• Nếu a[L] dương thì nó đã đứng đúng phía, L++.
• Nếu gặp a[L] < 0 thì đứng lại tại đó, xét sang a[R]: nếu a[R] dương thì swap(a[L], a[R]) rồi L++, R--; còn a[R] âm thì nó đã đứng đúng phía cuối, chỉ cần R--.
• Cứ thế đến khi L >= R thì dừng.

Mỗi bước lặp, L tăng hoặc R giảm (hoặc cả hai), nên tổng số bước không quá $n$ ⇒ $O(N)$. Bạn học viên hỏi mình hiểu đúng ý luôn: "tại nó duyệt từ 2 phía vô thôi ạ" 😁.

Bước 2: Đưa số âm vào các vị trí lẻ

Sau bước 1, mảng có dạng: $P$ số dương ở các vị trí $0..P-1$, rồi tới các số âm ở $P..n-1$. Nguyên tắc của mảng kết quả: vị trí chẵn phải là số dương, vị trí lẻ phải là số âm (cho tới khi một loại hết).

Vậy ta dùng con trỏ i chạy trên các vị trí lẻ $1, 3, 5, \ldots$ (đang là số dương, đứng sai chỗ) và con trỏ j chỉ vào số âm đầu tiên chưa dùng (ban đầu $j = P$). Mỗi lần swap(a[i], a[j]): vị trí lẻ $i$ nhận được số âm, còn số dương bị đổi ra thì nằm ở vị trí $j$, rồi i += 2, j++. Dừng khi:

• i >= j: không còn số dương nào đứng sai ở vị trí lẻ nữa, phần sau toàn số âm (âm dư nằm cuối), hoặc
• j == n: số âm đã dùng hết, phần sau toàn số dương (dương dư nằm cuối).

Vì sao đúng?

Trước mỗi lần đổi chỗ luôn có: đoạn $[0, i)$ đã xen kẽ đúng, đoạn $[i, j)$ toàn số dương, đoạn $[j, n)$ toàn số âm. Đổi a[i] (dương) với a[j] (âm) thì vị trí $i$ thành âm, vị trí $i+1$ vẫn là dương (đúng vị trí chẵn), số dương mới chuyển tới $j$ nằm trong đoạn dương, nên tính chất vẫn giữ nguyên sau khi i += 2, j++. Mỗi lần lặp $j$ tăng 1 ⇒ tổng cộng không quá $n$ lần ⇒ $O(N)$.

Cách mình hướng dẫn lúc nhắn tin

Lúc trao đổi với bạn học viên, ở bước 2 mình hướng dẫn: cho L chạy từ đầu, R từ cuối; gặp vị trí lẻ mà là số dương thì đổi với số âm ở a[R] rồi R--; khi L đi vào vùng số âm mà gặp vị trí chẵn là số âm thì reset lại R = n - 1 (vì các số dương vừa bị đẩy về cuối), lưu lại vị trí nhỏ nhất R đã đứng trước đó, L chạm tới ngưỡng này thì dừng. Với ví dụ 1 và các trường hợp số âm nhiều hơn hoặc bằng số dương thì cách đó cho kết quả đúng. Nhưng khi viết bài này mình kiểm tra lại bằng máy với mọi mảng nhỏ thì cách "reset R" bị sai khi số dương nhiều hơn số âm, ví dụ 1 2 3 4 -5 -6 -7. Nên trong bài mình trình bày cách dùng con trỏ j ở trên: cùng tư tưởng hai con trỏ nhưng gọn hơn và đúng với mọi trường hợp.

Minh hoạ 2 bước

Ô xanh là số dương, ô đỏ là số âm, ô viền cam là các ô con trỏ đang chỉ tới. Em nhập mảng rồi bấm Tiếp để xem từng bước:

Mảng a

Ví dụ nhanh:

Source code để các bạn tham khảo nếu làm theo hướng này:

#include <iostream>
using namespace std;

void Cau3(int a[], int n){
    // Bước 1: dồn số dương về đầu, số âm về cuối
    int L = 0, R = n - 1;
    while(L < R){
        if(a[L] > 0){
            L++;
        }
        else if(a[R] > 0){
            swap(a[L], a[R]);
            L++;
            R--;
        }
        else{
            R--;
        }
    }
    // Bước 2: đưa số âm vào các vị trí lẻ 1, 3, 5...
    int j = 0;
    while(j < n && a[j] > 0){
        j++;
    }
    for(int i = 1; i < j && j < n; i += 2){
        swap(a[i], a[j]);
        j++;
    }
}

int main(){
    int n;
    cin >> n;
    int *a = new int[n];
    for(int i = 0; i < n; ++i){
        cin >> a[i];
    }
    Cau3(a, n);
    for(int i = 0; i < n; ++i){
        cout << a[i] << " ";
    }
    delete[] a;
    return 0;
}

import sys


def Cau3(a, n):
    # Bước 1: dồn số dương về đầu, số âm về cuối
    L, R = 0, n - 1
    while L < R:
        if a[L] > 0:
            L += 1
        elif a[R] > 0:
            a[L], a[R] = a[R], a[L]
            L += 1
            R -= 1
        else:
            R -= 1
    # Bước 2: đưa số âm vào các vị trí lẻ 1, 3, 5...
    j = 0
    while j < n and a[j] > 0:
        j += 1
    i = 1
    while i < j and j < n:
        a[i], a[j] = a[j], a[i]
        i += 2
        j += 1


data = sys.stdin.buffer.read().split()
n = int(data[0])
a = list(map(int, data[1:1 + n]))
Cau3(a, n)
print(*a)

Giải thích một số chỗ trong code ở trên:

1. Phần bước 1 chính là đoạn code bạn học viên cài theo hướng dẫn của mình (mình chỉ viết gọn lại).
2. Vòng while(j < n && a[j] > 0) tìm vị trí số âm đầu tiên sau bước 1, tức $j = P$ (số lượng số dương).
3. Mảng nhập vào được cấp phát động bằng new int[n] để đúng mẫu hàm void Cau3(int a[], int n) của đề. Đây là mảng dữ liệu đề cho chứ không phải mảng phụ; trong hàm Cau3 ta chỉ dùng vài biến đơn.
4. Code coi số $0$ (nếu có) như số âm vì điều kiện là a[...] > 0; đề chỉ có số dương và số âm nên không ảnh hưởng.

C++▶ Chạy tay từng dòng codeBước 1 dồn dương về đầu bằng L, R; bước 2 đổi số âm vào các vị trí lẻ bằng i, j.

Dữ liệu vào (stdin) – sửa thoải mái10 8 -8 -7 -9 3 3 2 -2 -7 10

Dữ liệu mẫu:

1#include <iostream>

2using namespace std;

3

4void Cau3(int a[], int n){

5 // Bước 1: dồn số dương về đầu, số âm về cuối

6 int L = 0, R = n - 1;

7 while(L < R){

8 if(a[L] > 0){

9 L++;

10 }

11 else if(a[R] > 0){

12 swap(a[L], a[R]);

13 L++;

14 R--;

15 }

16 else{

17 R--;

18 }

19 }

20 // Bước 2: đưa số âm vào các vị trí lẻ 1, 3, 5...

21 int j = 0;

22 while(j < n && a[j] > 0){

23 j++;

24 }

25 for(int i = 1; i < j && j < n; i += 2){

26 swap(a[i], a[j]);

27 j++;

28 }

29}

30

31int main(){

32 int n;

33 cin >> n;

34 int *a = new int[n];

35 for(int i = 0; i < n; ++i){

36 cin >> a[i];

37 }

38 Cau3(a, n);

39 for(int i = 0; i < n; ++i){

40 cout << a[i] << " ";

41 }

42 delete[] a;

43 return 0;

44}

ChậmVừaNhanhRất nhanh

Đánh giá độ phức tạp của cách làm này:

• Không gian: ngoài mảng đề cho, hàm chỉ dùng vài biến L, R, i, j ⇒ $O(1)$, đúng yêu cầu không dùng mảng phụ.
• Thời gian: bước 1 mỗi lần lặp L tăng hoặc R giảm ⇒ tối đa $n$ lần; bước 2 tìm $j$ và mỗi lần đổi chỗ $j$ tăng 1 ⇒ tối đa $n$ lần. Tổng cộng $\Theta(n)$ đúng như đề yêu cầu.

Không gian$O(1)$

Thời gian$\Theta(N)$

Thì thực ra mình cũng nháp mấy cái trên giấy là thấy quy luật này rồi 😁. Các bạn cũng tập thói quen nháp ra vài ví dụ nhỏ, nhìn xem sau mỗi bước mảng có dạng gì là sẽ thấy hướng đi nhé.

Ghi chú của mình: code C++ và Python của cả 2 cách đã được kiểm tra với 3 ví dụ của đề và 400 bộ test ngẫu nhiên ($n \le 15$) bằng chương trình kiểm tra kết quả (đủ các số ban đầu, xen kẽ đúng, phần dư cùng dấu) – đúng hết. Mình cũng đã thử cách 2 với tất cả các mảng có $n \le 9$ (mọi cách đặt dấu) – đúng hết. Với $n = 10^6$, riêng hàm Cau3 của cách 2 chạy khoảng 0,03 giây (C++) và 0,5 giây (Python); cả chương trình thì lâu hơn (C++ khoảng 1,1 giây, Python khoảng 5 giây) do phần lớn thời gian là đọc và in một triệu số.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇