Số lượng phân biệt tuyệt đối trong một mảng đã sắp xếp?

Trong phần này chúng ta sẽ xem cách đếm có bao nhiêu phần tử có giá trị tuyệt đối khác nhau? Giả sử trong một mảng có ít phần tử như {5, 5, 6, -5, 8, 2, -2, 1} nên có 8 phần tử. Nhưng có 5 phần tử {5, 6, 8, 2, 1} khác biệt. -5 và 5 không được coi là khác nhau, chúng giống nhau vì giá trị tuyệt đối của chúng là như nhau.

Để giải quyết vấn đề này, chúng ta sẽ sử dụng cấu trúc Đặt dữ liệu. Trong bộ các phần tử trùng lặp không được phép. Và khi chúng tôi chèn mục vào tập hợp, chúng tôi sẽ chỉ đẩy giá trị tuyệt đối.

Thuật toán

AbsolDistinctCount (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

Ví dụ

#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);
}

Đầu ra

Absolute Distinct Count: 5