นับไม่ซ้ำกันแน่นอนในอาร์เรย์ที่เรียงลำดับ?

ในส่วนนี้เราจะมาดูวิธีการนับจำนวนองค์ประกอบที่มีค่าสัมบูรณ์แตกต่างกันอย่างไร สมมติว่าในอาร์เรย์มีองค์ประกอบไม่กี่อย่าง เช่น {5, 5, 6, -5, 8, 2, -2, 1} จึงมี 8 องค์ประกอบ แต่มีองค์ประกอบ 5 ประการ {5, 6, 8, 2, 1} ที่แตกต่างกันออกไป -5 และ 5 ไม่ถือว่าต่างกัน โดยมีค่าสัมบูรณ์เท่ากัน

เพื่อแก้ปัญหานี้ เราจะใช้ Set data-structure ไม่อนุญาตให้ใช้องค์ประกอบที่ซ้ำกันในชุด และเมื่อเราใส่ Item เข้าไปใน Set เราจะทำการ Push เฉพาะค่า Absolute เท่านั้น

อัลกอริทึม

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

ตัวอย่าง

#include<iostream>
#include<set>
#include<cmath>
using namespace std;
int absoluteDistinctCount(int arr[], int n){
   set<int> s;
   for(int i = 0; i<n; i++){
      s.insert(abs(arr[i])); //insert the absolute value
   }
   return s.size();
}
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