【算法题】求数组中唯一重复的元素

66 阅读 0 评论 44 点赞

我是靠谱客的博主风中小霸王，最近开发中收集的这篇文章主要介绍【算法题】求数组中唯一重复的元素，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

在网上看到一个这样的题：
一个数组中含有1001个元素，存放了1,2,3...1000和一个重复的数。只有唯一一个数是重复的，其它均只出现一次。要求设计一个算法找出这个重复的数，要求：每个数组元素只能访问一次，不用辅助存储空间。

解法一：
最简单的方法是，先求出1...1000的和（用公式：n(n+1)/2）sum1，然后求出arr[0]...arr[1000]的和sum2，（sum2-sum1）便是要求的结果。该方法只用遍历数组一次即可。

解法二：
可以用bit-map，先将bit-map所有位标记为1，然后将数组循环一遍，依次将每个元素读入bit-map，如果对应位为0，则标记为1，如果对应位为1，则该数便是要求的结果。该方法也只用遍历数组一次。但是，题目中要求不用辅助存储空间，而这里使用了bit-map为辅助存储空间，显然不符合要求，不过该方法的思想是不错的。而且当该数组的范围非常大时，用解法一进行求和时可能会溢出，而该解法却是不错的选择。

解法三：
本文其实想好好说说解法三，该方法是在网上看到的，觉得很巧妙也挺有意思，在这里跟大家分享一下。主要利用了公式：a ^ b ^ a = b。代码如下：

#include <iostream>
using namespace std;

int findRepeat(const int arr[], const size_t len)
{
    int res = arr[0];
    for (int i = 1; i < len; i++)
    {
	res ^= i;
	res ^= arr[i];
    }
    return res;
}

int main()
{
    int arr[6] = {1, 2, 3, 4, 5, 3};
    int res = findRepeat(arr, 6);
    cout << "The repeat number is : " << res << endl;
    return 0;
}

函数findRepeat中的res为异或的中间结果，res ^= i是异或1...1000每个数，res ^= arr[i]是异或arr[0]...arr[1000]每个元素，执行完for循环后，除了重复的那个数异或了3次外，其他所有的数异或了2次，因此res就是重复的那个数。例如，对于上面main函数中的测试数组，res的求值过程为：res = 1 ^ 1 ^ 2 ^ 2 ^ 3 ^ 3 ^ 4 ^ 4 ^ 5 ^ 5 ^ 3，结果为3。该解法也只用遍历数组一次，而且对于数组范围非常大时，不会出现溢出的情况。

当然还有很多其他的方法。