อาร์เรย์ (Array) คือชุดสมาชิกชนิดเดียวกัน อาร์เรย์ที่เรียงแล้ว (Sorted Array) คืออาร์เรย์ที่เรียงจากน้อยไปมากหรือมากไปน้อย
Distinct count คือจำนวนสมาชิกที่ไม่ซ้ำกัน Absolute distinct count คือ distinct count ของค่าสัมบูรณ์ (ค่าที่ไม่มีเครื่องหมาย)
ตัวอย่าง: Input: [-3, 0, 3, 6] → Output: 3 (ค่าสัมบูรณ์ที่ไม่ซ้ำ: 0, 3, 6)
วิธีที่ 1: ใช้ Set
Set เก็บค่าที่ไม่ซ้ำ ใส่ค่าสัมบูรณ์ของแต่ละสมาชิก แล้วคืนขนาดของ set
อัลกอริทึม
- สร้าง set ชนิดเดียวกับอาร์เรย์
- หาค่าสัมบูรณ์แต่ละตัวใส่ set (ซ้ำจะเก็บแค่ตัวเดียว)
- คืนขนาด set = จำนวนค่าสัมบูรณ์ที่ไม่ซ้ำ
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
int main() {
int arr[] = {-3, 0, 2, 6};
int n = sizeof(arr)/sizeof(arr[0]);
cout << "Count of absolute distinct values : ";
unordered_set<int> s;
for (int i = 0; i < n; i++)
s.insert(abs(arr[i]));
int nof = s.size();
cout<<nof;
return 0;
}
ผลลัพธ์
Count of absolute distinct values : 4
วิธีที่ 2: ใช้ตัวแปรนับและตรวจสอบอาร์เรย์
ใช้ตัวแปรเดียวแทน set วนลูปนับค่าที่ไม่ซ้ำ
ตัวอย่าง
#include <iostream>
using namespace std;
int main() {
int arr[] = {-5, -1, 0, 5, 8};
int n = sizeof(arr)/sizeof(arr[0]);
cout << "Count of absolute distinct values : ";
int count = n;
int i = 0, j = n - 1, sum = 0;
while (i < j) {
while (i != j && arr[i] == arr[i + 1]) count--, i++;
while (i != j && arr[j] == arr[j - 1]) count--, j--;
if (i == j) break;
sum = arr[i] + arr[j];
if (sum == 0) { count--; i++; j--; }
else if(sum < 0) i++;
else j--;
}
cout<< count;
return 0;
}
ผลลัพธ์
Count of absolute distinct values : 4
