数组唯一元素重复出现的

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

问题描述：给定包含101个元素的数组arr，数组中元素一定属于[1，100]，并且[1，100]之间的每个数都在arr中出现过。

解决方案：分析，数组中有101个元素，如果[1，100]之间的每个数出现一次，那就是100个元素了，剩下的那个元素就是唯一的重复出现的元素。我们可以通过遍历arr，得到arr中所有元素的总和，然后既然[1，100]之间的每个数出现一次，那么我们减去1+2+……+99+100的和，结果就是我们需要的唯一的重复出现的元素了。时间复杂度是O(n)。

#include
#define N 100

int array[101];
int findOnlyRepeat(int * a)
{
    int total_sum=0,sub_sum=0;
    for(int i=1;i<=N;i++)
    {
        sub_sum+=i;
        total_sum+=a[i-1];
    }
    return (total_sum+a[N]-sub_sum);
}
int main()
{
    //初始化数组,元素必定是1,...,100
    for(int i=1;i<=N;i++)
    {
        array[i-1]=i;
    }
    array[N]=90;//随便置一个数重复,就算是其它下标也行啊，只是测试

    int repeat=findOnlyRepeat(array);
    printf("the reapeat is %d\n",repeat);
    return 0;
}

2.找出数组中出现奇数次的元素

问题描述：现在有一个整数数组arr，其中的元素只有一个元素出现奇数次，请找出这个元素。

解决方案：对于任意一个数k，有k^k = 0，k^0 = k，所以将arr中所有元素进行异或，那么出现次数为偶数的元素异或后都变成了0，出现次数为奇数的元素异或后得到元素本身。下面写代码就很容易了~~时间复杂度是O(n)。

#include

//找出数组唯一的出现次数是奇数的元素,不能找出所有，
//用hash吧
int findTheOdd(int * a,int n)
{
    int ans=a[0];
    for(int i=1;i
    {
        ans^=a[i];
    }
    return ans;
}
int main()
{
    int a[13]={1,1,1,2,2,2,2,3,3,5,5,6,6};
    int odd=findTheOdd(a,13);
    printf("the number of odd is %d\n",odd);
    return 0;

}