原文:
给定一个大小为 n 的、 arr[] ，任务是找出给定数组中所有可能对的明显绝对差异。
示例:
输入: arr[] = { 1，3，6 } 输出: 2 3 5 解释:t8】abs(arr[0]–arr[1])= 2 abs(arr[1]–arr[2])= 3 abs(arr[0]–arr[2])= 5
输入: arr[] = { 5，6，7，8，14，19，21，22 } 输出:1 2 3 5 7 8 9 11 12 13 14 15 16 17
天真方法:解决这个问题最简单的方法是和中插入每对的绝对差。最后，打印集合的所有元素。 时间复杂度:o(n2 log(n)* 辅助空间: o(n 2 )
方法:上述方法可以使用进行优化。按照以下步骤解决问题:
- 初始化一个，比如 bset ，其中bset【i】检查数组中是否存在 i 。
- 遍历数组 arr[] 并将所有数组元素存储在 bset 中。
- 初始化一个，比如 diff ，其中diff【i】存储数组中是否存在任何值等于 i 的对的绝对差。
- 找到数组中最大的元素，说 max
- 迭代范围【0，最大】。在每次itht5】迭代中，检查bset【i】是否为真。如果发现为真，则使用diff = diff |(bset>>i)插入 i 与所有其他数组元素的绝对差。
- 最后，迭代范围【0，最大】，检查差值【i】是否为真。如果发现是真的，那就打印 i 。
下面是上述方法的实现:
c
// c program for the above approach
#include
using namespace std;
#define max 100005
// function to find all distinct
// absolute difference of all
// possible pairs of the array
void printuniqdif(int n, int a[])
{
// bset[i]: check if i is present
// in the array or not
bitset bset;
// diff[i]: check if there exists a
// pair whose absolute difference is i
bitset diff;
// traverse the array, arr[]
for (int i = 0; i < n; i ) {
// add in bitset
bset.set(a[i]);
}
// iterate over the range[0, max]
for (int i = 0; i <= max; i ) {
// if i-th bit is set
if (bset[i]) {
// insert the absolute difference
// of all possible pairs whose
// first element is arr[i]
diff = diff | (bset >> i);
}
}
// stores count of set bits
int x = bset.count();
// if there is at least one
// duplicate element in arr[]
if (x != n) {
cout << 0 << " ";
}
// printing the distinct absolute
// differences of all possible pairs
for (int i = 1; i <= max; i ) {
// if i-th bit is set
if (diff[i]) {
cout << i << " ";
}
}
}
// driver code
int main()
{
// given array
int a[] = { 1, 4, 6 };
// given size
int n = sizeof(a) / sizeof(a[0]);
// function call
printuniqdif(n, a);
return 0;
}
python 3
# python3 program for the above approach
max = 100005
# function to find all distinct
# absolute difference of all
# possible pairs of the array
def printuniqdif(n, a):
# bset[i]: check if i is present
# in the array or not
bset = [0 for i in range(33)]
# diff[i]: check if there exists a
# pair whose absolute difference is i
diff = 0
# traverse the array, arr[]
for i in range(n):
bset[a[i]] = 1
# iterate over the range[0, max]
d = 0
for i in range(1,33):
d = d | (bset[i]<> i
# print(bin(diff))
# stores count of set bits
x, y = bset.count(1), str(bin(diff)[2:])
# if there is at least one
# duplicate element in arr[]
if (x != n):
print(0, end=" ")
# printing the distinct absolute
# differences of all possible pairs
for i in range(1, len(y)):
# if i-th bit is set
if (y[i] == '1'):
print(i, end = " ")
# driver code
if __name__ == '__main__':
# given array
a = [1, 4, 6]
# given size
n = len(a)
# function call
printuniqdif(n, a)
# this code is contributed by mohit kumar 29
output:
2 3 5
时间复杂度:* o(n max)，其中 max 是数组中最大的元素。辅助空间:* o(最大)
麻将胡了pg电子网站的版权属于：月萌api www.moonapi.com，转载请注明出处
