使用 C++ 查找数组中唯一对的数量

我们需要适当的知识在 C++ 中的数组语法中创建几个唯一的对。在寻找唯一对的数量时,我们计算给定数组中的所有唯一对,即,可以形成所有可能的对,其中每对都应该是唯一的。例如 -

Input : array[ ] = { 5, 5, 9 }

Output : 4

Explanation : The number of all unique pairs are (5, 5), (5, 9), (9, 5) and (9, 9).

Input : array[ ] = { 5, 4, 3, 2, 2 }

Output : 16

寻找解决方案的方法

此解决方案有两种方法,它们是 -

蛮力方法

在这种方法中,我们将遍历每个可能的对,将这些对添加到一个集合中,最后找出该集合的大小。这种方法的时间复杂度是 O(n2 log n)。

示例

#include <bits/stdc++.h>

using namespace std;

int main () {

   int arr[] = { 5, 4, 3, 2, 2 };

   int n = sizeof (arr) / sizeof (arr[0]);

   // 声明集来存储对。

   set < pair < int, int >>set_of_pairs;

   for (int i = 0; i < n; i++)

      for (int j = 0; j < n; j++)

         set_of_pairs.insert (make_pair (arr[i], arr[j]));

   int result = set_of_pairs.size();

   cout <<"唯一对的数量: " << result;

   return 0;

}

输出结果
唯一对的数量: 16

上面代码的解释

在这段代码中,首先,我们声明一个集合变量,然后使用两个循环,遍历每个可能的对,并使用 i 和 j 将每一对插入集合中。然后我们正在计算集合的大小并打印结果。

有效的方法

另一种方法是先找出数组中唯一数字的个数;现在,每个其他唯一元素,包括其自身,都可以与任何其他唯一元素创建一对,因此唯一对的数量等于所有唯一数字的数量的平方。他的方法的时间复杂度是O(n).

示例

#include <bits/stdc++.h>

using namespace std;

int main () {

   int arr[] = { 5, 4, 3, 2, 2 };

   int n = sizeof (arr) / sizeof (arr[0]);

   // 声明集合来存储唯一元素。

   unordered_set < int >set_of_elements;

   // 在集合中插入元素。

   for (int i = 0; i < n; i++)

      set_of_elements.insert (arr[i]);

   int size = set_of_elements.size ();

   // 查找唯一对的数量

   int result = size * size;

   cout << "数组中唯一对的数量: " << result;

   return 0;

}

输出结果
唯一对的数量: 16

上面代码的解释

在这段代码中,我们声明了一个集合,然后遍历数组的每个元素,插入集合中的每个元素。之后,我们计算集合的大小,从公式n2中找到结果,并打印输出。

结论

在本文中,我们解决了在数组中找到唯一对的数量的问题,我们讨论了两种解决问题的方法,即简单和高效。在一个简单的方法中,我们将所有可能的对插入一个时间复杂度为 O(n2 log n) 的集合中,而在一个有效的方法中,我们找到所有唯一的数字,并用 n2 找到结果。我们可以用其他语言编写相同的程序,例如 C、java、python 和其他语言。希望这篇文章对您有所帮助。

以上是 使用 C++ 查找数组中唯一对的数量 的全部内容, 来源链接: utcz.com/z/352633.html

回到顶部