在 C++ 中的 2n+1 个整数元素的数组中查找单个
在这个问题中,我们得到一个由(2n+1)个整数值组成的数组。在所有这些值中,n个元素在数组中出现了两次,并且数组中只有一个元素出现了一次。我们的任务是在2n+1个整数元素的数组中查找单个元素。
让我们举个例子来理解这个问题,
输入
arr[] = {1, 3, 5, 6, 5, 1, 3}输出结果
5
解决方法
该问题的一个简单解决方案是对元素使用计数器。如果遇到元素,则存储其值和出现次数。在此搜索表中出现次数=1的元素之后。更有效的解决方案是使用XOR。在这里,我们将对数组的所有元素执行XOR。这个异或将使所有出现两次的元素都为0。唯一出现的元素是出现次数为1的元素。
这是因为XOR的属性是-
- a^a = 0 - a^0 = a
程序来说明我们的解决方案的工作,
示例
#includeusing 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