首页  >  文章  >  后端开发  >  使用C++找到数组中唯一配对的数量

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

WBOY
WBOY转载
2023-09-07 11:53:09507浏览

使用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]);
   // declaring set to store pairs.
   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 <<"Number of unique pairs : " << result;
   return 0;
}

输出

Number of unique pairs : 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]);

   // declaring set to store unique elements.

   unordered_set < int >set_of_elements;
   // inserting elements in the set.
   for (int i = 0; i < n; i++)
      set_of_elements.insert (arr[i]);

   int size = set_of_elements.size ();
   // finding number of unique pairs
   int result = size * size;

   cout << "Number of unique pairs in an array: " << result;
   return 0;
}

输出

Number of unique pairs : 16

上述代码的解释

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

结论

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

以上是使用C++找到数组中唯一配对的数量的详细内容。更多信息请关注PHP中文网其他相关文章!

声明:
本文转载于:tutorialspoint.com。如有侵权,请联系admin@php.cn删除