นับจำนวนค่าสัมบูรณ์ที่ไม่ซ้ำกันในอาร์เรย์ที่เรียงแล้ว

ในส่วนนี้เราจะดูวิธานับว่ามีสมาชิกกี่ตัวที่ค่าสัมบูรณ์ (absolute value) ไม่ซ้ำกัน สมมติอาร์เรย์ = {5, 5, 6, -5, 8, 2, -2, 1} มี 8 สมาชิก แต่ค่าสัมบูรณ์ที่ไม่ซ้ำกันมี 5 ค่า คือ {5, 6, 8, 2, 1} เพราะ -5 และ 5 มีค่าสัมบูรณ์เท่ากัน

วิธีแก้: ใช้ Set data structure ซึ่งไม่ยอมรับค่าซ้ำ เมื่อ insert ใส่ค่าสัมบูรณ์เข้าไป

อัลกอริทึม

absoluteDistinctCount(arr)

begin
    define set s;
    for each element e in arr, do
        insert |e| into s
    done
    return the number of elements of s
end

ตัวอย่างโค้ด (C++)

#include <iostream>
#include <set>
#include <cmath>
using namespace std;

int absoluteDistinctCount(int arr[], int n) {
    set s;
    for (int i = 0; i < n; i++) {
        s.insert(abs(arr[i]));
    }
    return s.size();
}

int main() {
    int arr[] = {5, 5, 6, -5, 8, 2, -2, 1};
    int n = (sizeof(arr))/(sizeof(arr[0]));
    cout << "Absolute Distinct Count: " << absoluteDistinctCount(arr, n);
}

ผลลัพธ์

Absolute Distinct Count: 5