我总结了一下我目前遇到过的数组里有重复数字的各种问题以及对应的求法

求数组中只出现一次的元素

1.一个数组中有一个数字只出现了一次，其余数字都出现了两次，找出这个数字
这道题没有学过异或相关知识的话，大概第一反应就是用暴力法(把每个数字都与后面的数字相比较)
毫无疑问这个方法非常直观，但是缺点也很明显：时间复杂度：O(N*N) 这不是一个让人满意的复杂度。
如果你了解异或的知识的话就不难发现以下两点事实：
对任意一个整数N，都有:N^N = 0；N^0 = N。其中^是异或运算符，了解了这么两点,事情就会变得简单：把数组里的所有元素都异或一遍，最后得出的结果刚好就是那个只出现一次的数字。

int FindTheOne(int *a,int lenth)//a是数组，len为数组长度
{
    int ret = 0;
    int i = 0;
    for(i = 0;i<len;i++)
    {
      ret^=a[i];
    }
    return ret;
}

2.一个数组中只有两个数字出现一次，其他所有数字都出现了两次，找出这两个数字
了解了上面的异或知识后，我们知道再像第一题那样操作的话，最得出的结果是这两个只出现一次的数字的异或值。
假设这两个数为a和b，最后的结果就是a^b，而且我们知道这个值绝对不为零（为什么？）
对于a^b，从低位到高位开始，找到第一个bit位为1的位置设定为第m位，这个第m位的1肯定来自a或者来自b，不可能同时a,b的第m位（从低到高位）都为1。这样，就可以根据这个第m位就可以把数组分为两个部分，一组为第m位为0，一组为第m位为1.这样，就把问题分解成了求两个数组中只出现一次的数字了。

int GetOnePos(int num) //从低位开始找到第一个位1的bit位
{  
    int index=1;  
    int i=0;  
    while(i<32)  
    {  
        if((num&(1<<i))==(1<<i))  
            break;  
        else  
        {  
            index++;  
            i++;  
        }  
    }  
    return index;  
}  
int IsBitOne(int num,int index) //判断给定位置的bit位是否为1
{  
    num=(num>>index);  
    return num&1;  
}  
void FindTheTwo(int *a,int len,int *num1,int *num2)
{//没法返回两个数，所以传地址进来直接赋值
    int result=0;
    assert(a&&num1&&num2);
    *num1=0;
    *num2=0;
    for(int i=0;i<len;i++)
        result^=a[i];
    int index=GetOnePos(result);
    for(i=0;i<len;i++)
        if(IsBitOne(a[i],index))
            (*num1)^=a[i];
    for(i=0;i<len;i++)
        if(!IsBitOne(a[i],index))
            (*num2)^=a[i];
}

3.一个数组中只有三个数字出现一次，其他所有数字都出现了两次，找出这三个数字
额看到这个问题我不知该说什么，因为这已经有点刁难人的意味在里面了，
但是我们还是按部就班的来，首先还是全部异或一遍，最后得到的结果是a^b^c,我们令x = a^b^c 不难知道x与a,b,c任何一个都不相等（为什么？）
证明：x^a,x^b,x^c中只有一个第m-bit位为1.
假设他们的第m位都为1，那么x的第m位为0，但是x=a^b^c其第m位肯定为1，所以假设不成立。
那么相反，假设x的第m位为1，a,b,c的第m位都为0，也不成立，因为x=a^b^c。
所以根据上面的反证法我们知道了x^a,x^b,x^c中只有一个第m位为1。那么这个问题就好办了。根据这个第m位找到第一个只出现一次的数字。然后剩下两个就是问题2所描述的问题。

int GetFirstBit(int num)  
{  
    return num&~(num-1);  
}  

void FindTheThree(int *a,int len,int *num1,int *num2,int *num3)  
{  
    int result_code=0;  
    assert(a&&num1&&num2&&num3);
    for(int i=0;i<n;i++)  
        result_code^=a[i];  
    int flag=0;  
    for(i=0;i<len;i++)  
        flag^=GetFirstBit(result_code^a[i]);  
    flag=GetFirstBit(flag);  
    *num1=0;  
    for(i=0;i<len;i++)  
    {  
        if(GetFirstBit(result_code^a[i])==flag)  
        {  
            (*num1)^=a[i];  
        }  
    }  
    for(i=0;i<len;i++)  
    {  
        if(a[i]==(*num1))  
        {  
            int temp=a[i];  
            a[i]=a[len-1];  
            a[len-1]=temp;  
            break;  
        }  
    }  
    FindTheTwo(a,len-1,num2,num3);  
}

求数组主元素

什么是主元素呢，就是指数组中出现次数超过数组长度一半的元素，这个问题之前我专门讨论过：
传送门：http://lrsand52m.top/2018/05/21/#more

求数组里的重复数字

1.求一个字符数组中的第一个重复的字符
最直接方法：暴力…不用多想，妥妥的O(N*N)
那么有木有O（N）的解法呢，当然有啦~（没有我就不写这个问题了哈哈）
首先我们知道字符型只占据8个比特位一个字节，最多能表示256种可能，所以我们利用哈希方法，建立一个表，存储对应字符的出现次数（遍历了一遍），再从头开始检索每个字符的次数（又遍历了一遍），第一个次数大于一的就是我们要找的啦（真简单）这个算法使用了常数级别的额外空间让算法实现了O(N)的时间复杂度，可以说相当强大了（有没有感觉这种方法与桶排序有异曲同工之妙？）。

char FindFirstDup(char *a,int len)
{
    int index[256] = {0};
    int i = 0;
    assert(a);
    for(i = 0;i<len;i++)
        index[a[i]+128]++;
    for(i = 0;i<len;i++)
        if(index[a[i]+128]>1)
            return a[i];
    perror("Dup not found");
    return a[0];
}

2.一个长度为N的数组，里面存有0 ~ N-2这些值，很明显，数组里必定存在重复元素，现在可以向你保证只有一个重复的元素，但是我们不保证其只出现两次，它可能出现很多次。例如int a[5] = {1,2,2,2,3};请找出这个重复的数字。
最直接方法：暴力…不用多想，妥妥的O(N*N) (嗯暴力还是能解决相当多的问题的- -！)
我觉得大家第一反应应该是想到了上面的哈希方法，建立一个长度N的哈希表，然后再…就解决了，这个方法时间复杂度O(N),空间复杂度O(N)，因为这里我们使用额外空间的长度不再是常数了。
那么···有木有空间复杂度O(LogN)或者O(1)的算法呢？
答案是有的，但是首先我们要了解一下抽屉原理：
有N本书要放进N-1个抽屉里，那么无论你怎么放，你都会发现至少有一个抽屉里装了不只一本书。这个原理非常简单，简单到什么程度呢？额就是我这么一说你就明白的程度，够简单吧？
然而就是这么简单的抽屉原理，这个题目都给我们出了简化版：题目相当于告诉我们只有一个抽屉里放了多本书，而其他抽屉要么只有一本，要么没放书。
如果现实中有人扔给了你这样一个问题你会怎么做呢？
很简单，你只需要打开每个抽屉，查看里面有几本书就行了。
但是在这里书和抽屉并不是对应着放的，我们又该怎么办呢？
额那么把书放进对应的抽屉不就好了吗？围观群众说道；
是的，就是这么简单！
我们对数组中的数字进行遍历并且这样操作：
1.数字等于下标值，代表书的位置正确，我们查看下一个；
2.数字不等于下标值，代表书的位置不对，我们需要调整：查看对应下标值位置上的数字，如果也对不上，那么交换。如果人家的位置是正确的…那么这个值显然就是你要找的重复值了！

int FindDupNum(int *a,int len)
{
    int i = 0;
    for(i = 0;i<len;i++)
    {
        if(a[i] != i)
        {
          if(a[a[i]] == a[i])
              return a[i];
          else
          {
              int t = a[i];
              a[i] = a[a[i]];
              a[t] = t;
              i--;
          }
        }
    }
    perror("The Dup Not found");
}

这样每一次交换都会使一个抽屉里装的书是对的，那么我们最多遍历一遍就可以找到这个重复的数字了，并且我们实现了空间复杂度O(1),时间复杂度O(N)。
由于我打字打的手有点累，这次就先写到这里吧，我说的并不是很系统请见谅~~