Giới thiệu
Trong bài viết này, chúng ta sẽ tìm hiểu các phương pháp đếm và liệt kê các phần tử khác nhau trong một mảng. Chúng ta sẽ cùng nhau khám phá thuật toán đơn giản nhưng hiệu quả để giải quyết bài toán này.
Đếm Các Phần Tử Khác Nhau
Đầu tiên, chúng ta sẽ xem xét một phương pháp dễ tiếp cận. Để đếm các phần tử khác nhau trong mảng, chúng ta sẽ duyệt qua từng phần tử từ đầu đến cuối mảng. Với mỗi phần tử, chúng ta sẽ kiểm tra xem có phần tử nào trước đó giống với phần tử hiện tại hay không. Nếu không có, chúng ta sẽ tăng số lượng phần tử khác nhau lên 1.
Ví dụ: Giả sử chúng ta có một mảng A[] = {1, 3, 4, 5, 5, 2, 4, 8, 1, 2, 3}. Khi xét phần tử A[4] = 5, các phần tử trước nó là {1, 3, 4, 5}. Ta thấy phần tử A[4] giống với một phần tử trong đoạn trước nó, do đó chúng ta không đếm thêm phần tử khác nhau trong mảng.
Dưới đây là đoạn mã minh hoạ cho thuật toán trên:
#include "stdio.h" int main(){ int n = 10; int a[10] = {1, 3, 4, 5, 5, 2, 4, 1, 2, 3}; int res = 0; for(int i = 0; i < n; i++){ int check = 1; for(int j = 0; j < i; j++){ if(a[i] == a[j]){ check = 0; break; } } if(check == 1){ ++res; } } printf("Số lượng giá trị khác nhau trong mảng: %d\n", res); return 0; }Liệt Kê Các Phần Tử Khác Nhau
Thuật toán để liệt kê các phần tử khác nhau trong mảng tương tự như thuật toán ở mục trước. Tuy nhiên, chúng ta sẽ liệt kê theo thứ tự xuất hiện trong mảng.
Nếu bạn muốn liệt kê theo thứ tự từ nhỏ đến lớn, bạn cần sắp xếp mảng trước khi áp dụng thuật toán này.
Dưới đây là đoạn mã minh hoạ cho thuật toán liệt kê các phần tử khác nhau trong mảng:
#include "stdio.h" int main(){ int n = 10; int a[10] = {1, 3, 4, 5, 5, 2, 4, 1, 2, 3}; for(int i = 0; i < n; i++){ int check = 1; for(int j = 0; j < i; j++){ if(a[i] == a[j]){ check = 0; break; } } if(check == 1){ printf("%d ", a[i]); } } return 0; }Tần Suất Của Phần Tử Trong Mảng
Bài toán này yêu cầu chúng ta liệt kê các giá trị xuất hiện trong mảng kèm theo số lần xuất hiện của chúng. Có hai cách để giải quyết bài toán này.
Cách thứ nhất là không sử dụng mảng phụ và cách thứ hai yêu cầu sử dụng một mảng phụ để truy vết.
Thuật toán 1:
- Duyệt qua từng phần tử trong mảng từ đầu đến cuối.
- Với mỗi phần tử, chúng ta sẽ kiểm tra xem có phần tử nào trước đó giống với phần tử hiện tại hay không. Nếu không có, chúng ta sẽ tăng số lần xuất hiện của phần tử đó lên 1.
- Duyệt các phần tử từ vị trí hiện tại + 1 đến cuối mảng và so sánh với phần tử hiện tại để đếm số lần xuất hiện của nó.
Dưới đây là đoạn mã minh hoạ cho thuật toán trên:
#include "stdio.h" int main(){ int n = 10; int a[10] = {1, 3, 4, 5, 5, 2, 4, 5, 2, 3}; for(int i = 0; i < n; i++){ int check = 1; for(int j = 0; j < i; j++){ if(a[i] == a[j]){ check = 0; break; } } if(check == 1){ int count = 1; for(int j = i + 1; j < n; j++){ if(a[i] == a[j]) ++count; } printf("%d xuất hiện %d lần\n", a[i], count); } } return 0; }Thuật toán 2:
Ý tưởng của thuật toán này là sử dụng một mảng đánh dấu ban đầu có tất cả các phần tử là 0 để đánh dấu.
- Duyệt qua từng phần tử ở vị trí i trong mảng A[]. Nếu mảng đánh dấu B[i] = 0, chúng ta sẽ tiến hành đếm tần suất.
- Duyệt các phần tử j trong đoạn từ i + 1 đến cuối mảng và so sánh với A[i]. Nếu A[i] = A[j], chúng ta sẽ tăng tần suất và cho B[j] = 1 để đánh dấu.
Dưới đây là đoạn mã minh hoạ cho thuật toán trên:
#include "stdio.h" int main(){ int n = 10; int a[10] = {1, 3, 4, 5, 5, 2, 4, 5, 2, 3}; int b[10] = {0}; for(int i = 0; i < n; i++){ if(b[i] == 0){ int count = 1; for(int j = i + 1; j < n; j++){ if(a[i] == a[j]){ ++count; b[j] = 1; } } printf("%d xuất hiện %d lần\n", a[i], count); } } return 0; }Hy vọng rằng bạn đã hiểu và áp dụng thành công các thuật toán này trong bài tập mảng 1 chiều của bạn.
Xem thêm bài giảng của mình về Mảng 1 Chiều: Hình ảnh chỉ mang tính chất minh họa
Đó là một số phương pháp để giải quyết bài tập mảng 1 chiều. Chúc bạn thành công!