Mảng là một tập hợp các phần tử của cùng một kiểu dữ liệu. A mảng được sắp xếp là một mảng có các phần tử được lưu trữ theo trình tự tăng dần hoặc giảm dần.
Số lượng riêng biệt là số phần tử không giống nhau.
Tổng số phân biệt tuyệt đối là tổng số giá trị tuyệt đối riêng biệt của các phần tử, tức là các phần tử không có dấu (giá trị không dấu).
Trong chương trình này, chúng ta sẽ tìm số đếm khác biệt tuyệt đối trong một mảng đã sắp xếp. tức là chúng tôi sẽ đếm số lượng giá trị khác biệt nếu giá trị tuyệt đối của mỗi phần tử của mảng được xem xét.
Ví dụ,
Input : [-3 , 0 , 3 , 6 ] Output : 3
Có 3 giá trị tuyệt đối khác nhau trong mảng, các phần tử là 0, 3 và 6.
Để giải quyết vấn đề này, chúng tôi có các phương pháp, sử dụng các cách khác nhau.
Bằng cách sử dụng một bộ
Một tập hợp luôn chứa phần tử riêng biệt. vì vậy chúng tôi sẽ kiểm tra các giá trị tuyệt đối trong tập hợp và nếu nó không có sẵn thì khi nào sẽ thêm phần tử vào tập hợp. và trả về kích thước của tập hợp.
Thuật toán -
-
Tạo một tập hợp có cùng kiểu dữ liệu như mảng.
-
Tìm giá trị tuyệt đối của mỗi phần tử và lưu trữ các phần tử trong mảng. Tập hợp sẽ lưu trữ một giá trị duy nhất ngay cả khi có nhiều giá trị.
-
Sau khi tất cả các phần tử được nhập. Trả về độ dài của tập hợp. Điều này sẽ cung cấp cho số lượng các phần tử riêng biệt là mảng.
Ví dụ
#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;
} Đầu ra
Count of absolute distinct values : 4
Sử dụng biến đếm và kiểm tra mảng
Phương pháp này chỉ sử dụng một biến duy nhất thay vì một tập hợp. Chúng tôi sẽ cung cấp cho bạn một biến đếm để đếm các phần tử riêng biệt của mảng.
Ví dụ
#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;
} Đầu ra
Count of absolute distinct values : 4