找出数组中唯一的重复元素

57 阅读 0 评论 38 点赞

我是靠谱客的博主酷酷玉米，最近开发中收集的这篇文章主要介绍找出数组中唯一的重复元素，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目：数组 arr[N]，1 至 N 这 N - 1 个数存放在 arr[N] 中，其中某个数重复一次，写一个函数，找出重复的数字。要求每个数组元素只能访问一次，不用辅助存储空间。
分析：由于题目要求每个数组元素只能访问一次，不用辅助存储空间，可以从原理上入手，采用数学求和法，因为只有一个数字重复一次，而数又是连续的，根据累加和原理，对数组的所有项求和，然后减去 1 至 N - 1 的和，即为所求的重复数。

#include <iostream>
#define SUM(x) (x*(x+1)/2)

int findData(int arr[], int N)
{
    int sum = 0;
    for (int i = 0; i < N; i++)
        sum += arr[i];

    int sum2 = SUM((N-1)); // 此处的N-1，一定要用小括号括起来。

    return (sum - sum2);

}

int main(int argc, const char * argv[]) {

    int arr[] = {1,2,5,6,2,3,4,7};
    int len = sizeof(arr)/sizeof(int);

    printf("唯一重复的元素是 %dn", findData(arr, len));
    return 0;
}

拓展：如果题目没有要求每个数组元素只能访问一次，并且也可以使用辅助空间，还可以使用以下方法来求解。
（1）异或法
根据异或法的计算方式，每两个相异的数执行异或运算之后，结果为1；每两个相同的数异或之后，结果为0，所以数组 arr[N] 中的 N 个数异或结果与 1 至 N - 1 异或的结果再做异或，得到的值即为所求。
设重复数为 A，其余 N - 2 个数异或结果为 B，N 个数异或结果为 A^A^B，1 至 N - 1 异或结果为 A^B，由于异或满足交换律和结合律，且 X^X = 0，0^X = X，则有 (A^B)^(A^A^B) = A^B^B = A。

（2）Hash法
<1> 首先，数组元素的取值范围是 1 ~ N - 1，其中最大的数值为 N - 1，所以要申请一个长度为 N 的新数组（即按照集合中最大元素max创建一个长度为max+1的新数组），并将新数组元素全部初始化为0。
<2> 然后从头开始遍历原数组arr[N]，取每个数组元素 arr[ i ] 的值，将新数组中“以该值作为下标的元素“置1，如果已经置过1了，那么该数就是重复的数。空间复杂度为O(N)。

备注：Hash法和位图法(bitmap) 的比较
<1> 上述这种给新数组“初始化时置零、其后置一“的做法，类似于位图的处理方法，所以有人也称上述方法为－－位图法。
<2> 所谓bitmap就是用一个bit位来标记某个元素对应的value，而key即是这个元素。由于采用bit为单位来存储数据，因此在可以大大的节省存储空间。
<3> 位图法，由于每个数都是互斥的，所以它本身就是一个最好的散列（即使用的也是hash映射），所以位图法也可算作hash算法。
<4> 位图通过使用位数组来表示某些元素是否存在，位数组中的元素取值非0即1，没有其他可能，而且真正使用位图法时，一定会涉及到位运算，如’ | ’ 、’ & ‘和‘<< ’ 等位运算。
<5> 如果只是使用了位运算中“非0即1“的思想来判重，而没有使用“位数组＋位运算“，那么我认为称呼这类方法为hash法更合适一些，不应该称为位图法。
<6> 因为需要用到位运算，所以位图法一般只适用于“非重复的正整数的排序“、查找、判重、删除。