Tìm phần tử xuất hiện nhiều hơn một lần trong mảng (C)

Ví dụ

Input: arr[] = {5, 11, 11, 2, 1, 4, 2}
Output: 11 2

Phương pháp 1: Mảng đếm (Counting) - O(n) time, O(max) space

Phù hợp khi giá trị phần tử không quá lớn.

int count[max_val+1] = {0};
for i = 0 to n-1:
    count[arr[i]]++
for i = 0 to max_val:
    if count[i] > 1: print i

Phương pháp 2: Lồng vòng lặp - O(n²) time, O(1) space

for i = 0 to n-1:
    for j = i+1 to n-1:
        if arr[i] == arr[j]: print arr[i]; break

Code C (Phương pháp mảng đếm)

#include <stdio.h>
#include <stdlib.h>

int main() {
    int arr[] = {21, 87, 212, 109, 41, 21};
    int n = sizeof(arr)/sizeof(arr[0]);

    // Tìm max để cấp phát mảng đếm
    int max_val = arr[0];
    for (int i = 1; i < n; i++)
        if (arr[i] > max_val) max_val = arr[i];

    int *count = (int*)calloc(max_val + 1, sizeof(int));
    if (!count) return 1;

    printf("Repeated elements: ");
    for (int i = 0; i < n; i++) {
        if (count[arr[i]] == 1)
            printf("%d ", arr[i]);
        count[arr[i]]++;
    }
    printf("\n");

    free(count);
    return 0;
}

Kết quả

Repeated elements: 21

Lưu ý

• Code gốc dùng n=7 nhưng mảng chỉ 6 phần tử → đã sửa
• Cần free() bộ nhớ đã cấp phát
• Với giá trị lớn/âm, dùng hash table hoặc sắp xếp trước