Đếm số giá trị tuyệt đối khác nhau trong mảng đã sắp xếp

Trong phần này chúng ta sẽ xem cách đếm bao nhiêu phần tử có giá trị tuyệt đối khác nhau. Giả sử trong một mảng có vài phần tử như {5, 5, 6, -5, 8, 2, -2, 1}, vậy có 8 phần tử. Nhưng có 5 phần tử {5, 6, 8, 2, 1} là khác nhau. -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 giống nhau.

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

Thuật toán

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

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

Kết quả

Absolute Distinct Count: 5