Đếm giá trị tuyệt đối phân biệt trong mảng đã sắp xếp C++

Cho mảng đã sắp xếp, đếm số giá trị tuyệt đối phân biệt (distinct absolute values).

Ví dụ

Input: [-3, 0, 3, 6] → Output: 3 (giá trị: 0, 3, 6)

Cách 1: Dùng unordered_set (O(n) time, O(n) space)

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

int countDistinctAbs(const vector<int>& a) {
    unordered_set<int> s;
    for (int x : a) s.insert(abs(x));
    return s.size();
}

Cách 2: Hai con trỏ (Two Pointers) – O(n) time, O(1) space

Tận dụng mảng đã sắp xếp: so sánh abs(arr[left]) và abs(arr[right]).

int countDistinctAbsTwoPtr(const vector<int>& a) {
    int n = a.size();
    int left = 0, right = n - 1;
    int count = 0;
    int prev_left = INT_MAX, prev_right = INT_MIN;
    
    while (left <= right) {
        int absL = abs(a[left]);
        int absR = abs(a[right]);
        
        if (absL > absR) {
            if (absL != prev_left) { count++; prev_left = absL; }
            left++;
        } else if (absR > absL) {
            if (absR != prev_right) { count++; prev_right = absR; }
            right--;
        } else { // absL == absR
            if (absL != prev_left && absL != prev_right) { count++; }
            prev_left = prev_right = absL;
            left++; right--;
        }
    }
    return count;
}

Chương trình hoàn chỉnh

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

int main() {
    vector<int> arr = {-5, -1, 0, 5, 8};
    cout << "Cach 1 (set): " << countDistinctAbs(arr) << "\n";
    cout << "Cach 2 (two pointers): " << countDistinctAbsTwoPtr(arr) << "\n";
    return 0;
}

Kết quả

Cach 1 (set): 4
Cach 2 (two pointers): 4