Đếm số phần tử bất thường (anomaly) trong mảng C++

Một phần tử được gọi là anomaly (bất thường) nếu khoảng cách tuyệt đối giữa nó và mọi phần tử khác trong mảng đều lớn hơn k.

Ví dụ

Đầu vào: arr = [3, 1, 5, 7], k = 1

Đầu ra: 4 (tất cả 4 phần tử đều là anomaly vì khoảng cách giữa bất kỳ cặp nào ≥ 2 > 1)

Thuật toán

• Duyệt từng phần tử arr[i].
• Kiểm tra với mọi arr[j] (j ≠ i): nếu tồn tại |arr[i] - arr[j]| <= k thì arr[i] không phải anomaly.
• Nếu không tìm thấy cặp nào thỏa mãn → tăng đếm.

Triển khai C++

#include <bits/stdc++.h>
using namespace std;

int getAnomaliesCount(int arr[], int n, int k) {
    int count = 0;
    for (int i = 0; i < n; i++) {
        bool isAnomaly = true;
        for (int j = 0; j < n; j++) {
            if (i != j && abs(arr[i] - arr[j]) <= k) {
                isAnomaly = false;
                break;
            }
        }
        if (isAnomaly) count++;
    }
    return count;
}

int main() {
    int arr[] = {3, 1, 5, 7};
    int n = 4, k = 1;
    cout << getAnomaliesCount(arr, n, k) << endl; // Output: 4
    return 0;
}

Kết quả

4

Độ phức tạp: O(N²). Có thể tối ưu bằng sắp xếp + hai con trỏ về O(N log N).