首页 > 代码库 > 唯一的重复元素

唯一的重复元素

1. 问题描述

  数组a[n],1到n-1这n-1个数放在这个数组中,其中有一个数重复一次。写一个算法找出这个数来。


2. 方法与思路

2.1 累加和法

  采用数学求和的方法,由于数组中只有一个数是重复的,且又是连续的,根据累加和原理,对数组求和然后减去1到n-1的和即为所求的重复数。 

int OnlyParameter1(int a[],int len)
{
    int i,res=0;
    for(i=0;i<len-1;i++)
    {
        res+=a[i]-(i+1);
    }
    res+=a[len-1];
    return res;
}

2.2 位图法

  先设一个标记数组mark,长度为n,然后将这个数组的全部元素置为0。循环遍历数组a,判断mark[a[i]]是否为1,若是则返回这个重复的元素,否则将mark[a[i]]标记为1。 

int OnlyParameter(int a[],int n)
{
    int res=0;
    int mark[n-1];
    for(int i=0;i<n;i++)
        mark[i]=0;
    for(int i=0;i<n;i++)
    {
        if(mark[a[i]]==1)
        {
            res=a[i];
            break;
        }
        else
        {
            mark[a[i]]=1;
        }
    }
    return res;
}

 

2.3 异或法

  根据异或公式:a^b = 1; a ^a = 0;0^a = a。 数组a[n]中n个数异或的结果再与1到n-1异或的结果异或即为所求的重复数。说明:设重复数为a,其余n-2个数异或结果为b,n个数的异或结果为a^a^b,1到n-1的异或结果为a^b,则(a^b)^(a^a^b) = a。 

int OnlyRepeat_xor(int a[], int len)
{
    int i,re = 0;

    for(i = 0; i < len; i++)
        re ^= a[i];

    for(i = 1; i < len; i++)
        re ^= i;

    return re;
}

 

唯一的重复元素