Hướng dẫn giải của Sắp xếp ma trận 1
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.
Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.
Bạn phải đăng nhập để mở lời giải này.
Đăng nhập
Tác giả: Hiếu Nguyễn
, , ,
Hiểu bài toán
Cho ma trận số nguyên có m dòng và n cột. Yêu cầu chỉ sắp xếp hàng thứ i (tính từ 1) tăng dần, giữ nguyên các hàng còn lại. Sau đó in ra ma trận kết quả.
Các cách tiếp cận
Cách Bubble Sort trực tiếp
#include <stdio.h>
int main() {
int m, n, i;
scanf("%d%d%d", &m, &n, &i);
int a[m][n];
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
scanf("%d", &a[r][c]);
}
}
int row = i - 1;
// Bubble sort ascending
for (int x = 0; x < n - 1; x++) {
for (int y = x + 1; y < n; y++) {
if (a[row][x] > a[row][y]) {
int temp = a[row][x];
a[row][x] = a[row][y];
a[row][y] = temp;
}
}
}
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
printf("%d ", a[r][c]);
}
printf("\n");
}
return 0;
}
- Time Complexity: O(m*n + n^2)
- Space Complexity: O(m*n)
Đọc dữ liệu vào ma trận 2 chiều. Duyệt hàng thứ i - 1 với thuật toán Bubble Sort (hoặc Selection Sort) để sắp xếp tăng dần. In toàn bộ ma trận. Code sử dụng Bubble Sort lồng nhau: vòng lặp ngoài điều khiển số phần tử đã được 'nổi' lên cuối, vòng lặp trong so sánh và hoán đổi các cặp phần tử liền kề.
Cách Sử dụng mảng phụ
#include<stdio.h>
#include<limits.h>
#define Nmax 100010
void sort(int *a,int n)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n-i;j++)
{
if(a[j]>a[j+1])
{
int t=a[j];
a[j]=a[j+1];
a[j+1]=t;
}
}
}
}
int main()
{
int n,m,k,a[110][110],b[110];
scanf("%d%d%d",&m,&n,&k);
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
scanf("%d",&a[i][j]);
}
}
for(int i=1;i<=n;i++) b[i]=a[k][i];
sort(b,n);
for(int i=1;i<=n;i++) a[k][i]=b[i];
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
printf("%d ",a[i][j]);
}
printf("\n");
}
return 0;
}
- Time Complexity: O(m*n + n^2)
- Space Complexity: O(m*n)
Giống cách 1 nhưng copy hàng cần sắp xếp vào mảng phụ 'b', sort mảng 'b', rồi gán lại vào hàng đó. Điều này giúp hàm sort tách biệt và có thể tái sử dụng, nhưng về bản chất thuật toán vẫn là Bubble Sort O(n^2).
Cách Tối ưu với qsort (C Standard Library)
#include <stdio.h>
#include <stdlib.h>
int cmp(const void *a, const void *b) {
return (*(int*)a - *(int*)b);
}
int main() {
int m, n, i;
scanf("%d%d%d", &m, &n, &i);
int a[m][n];
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
scanf("%d", &a[r][c]);
}
}
int row = i - 1;
qsort(a[row], n, sizeof(int), cmp);
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
printf("%d ", a[r][c]);
}
printf("\n");
}
return 0;
}
- Time Complexity: O(m*n + n log n)
- Space Complexity: O(m*n)
Sử dụng hàm qsort có sẵn trong thư viện chuẩn của C để sắp xếp hàng thứ i. Đây là cách hiệu quả nhất về thời gian thực thi (do dùng thuật toán Merge Sort hoặc Quick Sort tối ưu). Chỉ cần truyền con trỏ đến phần tử đầu tiên của hàng và số lượng phần tử (n).
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(m*n + n^2) | O(m*n) | Bubble Sort trực tiếp |
| 2 | O(m*n + n^2) | O(m*n) | Sử dụng mảng phụ |
| 3 | O(m*n + n log n) | O(m*n) | Tối ưu với qsort (C Standard Library) |
Bài học kinh nghiệm
- Bài toán chỉ thay đổi một hàng duy nhất, các hàng khác giữ nguyên.
- Chỉ số hàng trong input bắt đầu từ 1, cần chuyển về 0 nếu dùng mảng C/C++.
- Mảng 2 chiều lưu trữ liên tục trong bộ nhớ, có thể truy cập hàng bằng con trỏ hoặc chỉ số.
Lỗi thường gặp
- Lỗi chỉ số:混淆 hàng thứ i (1-based) với chỉ số mảng (0-based). Ví dụ input '1' tương ứng với index 0.
- In sai format: In thừa dấu cách cuối dòng hoặc thiếu dòng mới '\n' ở cuối.
- Quên khai báo kích thước mảng đủ lớn: Nên dùng kích thước cố định an toàn (ví dụ 110) hoặc mảng động theo input.
Bình luận