好资源导航 » 文章资讯 » 在 C++ 中的 2n+1 个整数元素的数组中查找单个

在 C++ 中的 2n+1 个整数元素的数组中查找单个

2023-06-16 12:26:03 70

在这个问题中，我们得到一个由(2n+1)个整数值组成的数组。在所有这些值中，n个元素在数组中出现了两次，并且数组中只有一个元素出现了一次。我们的任务是在2n+1个整数元素的数组中查找单个元素。

让我们举个例子来理解这个问题，

输入

arr[] = {1, 3, 5, 6, 5, 1, 3}

输出结果

解决方法

该问题的一个简单解决方案是对元素使用计数器。如果遇到元素，则存储其值和出现次数。在此搜索表中出现次数=1的元素之后。更有效的解决方案是使用XOR。在这里，我们将对数组的所有元素执行XOR。这个异或将使所有出现两次的元素都为0。唯一出现的元素是出现次数为1的元素。

这是因为XOR的属性是-

- a^a = 0
- a^0 = a

程序来说明我们的解决方案的工作，

示例

#include 
using namespace std;
int findSingleValue(int arr[], int n) {
   int element = 0;
   for (int i = 0; i < n; i++)
      element = element ^ arr[i];
   return element;
}
int main() {
   int arr[] = { 1, 3, 5, 6, 5, 1, 3 };
   int n = sizeof(arr) / sizeof(arr[0]);
   cout<<"单次出现的数组元素是 "<输出结果单次出现的数组元素是 6

返回顶部
514930285
czq8825@qq.com

在 C++ 中的 2n+1 个整数元素的数组中查找单个

输入

解决方法

示例

热门推荐

随机推荐