算法分享之六种方法找出数组卧底

如果一个长度为的数组，包含了数字到的每个数字，但是有一个数字势必会重复出现，我们可以把这个唯一出现两次的数字看成卧底，如何找出这个卧底，下面提供6种思路，可以参考牛客网下面这道题 ，也可以参考这篇题解 。

方法一：排序法

要解决这个问题，我们首先想到的是将这个数组排序，然后重复的数字就会相邻，检查相邻两个数字是否重复就可以找到这个重复数字了。

利用sort函数对数组排序，遍历数组，相邻两个数相同则找到所求。

  class Solution {
  public:
      int search(int n, vector<int>& a) {
          sort(a.begin(), a.end()); //排序
          for(int i = 1; i <= n; i++){ //找相邻重复
              if(a[i] == a[i - 1])
                  return a[i];
          }
          return 0;
      }
  };

方法二：哈希表

对于这种数字出现次数的问题，也可以用哈希表来记录数字出现的频率。

利用无序哈希表unordered_map记录所有数字，遍历数组每遇到一个数查看是否已经在哈希表中，如果在，则返回该数，说明这是第二次出现，如果不在则加入哈希表中。

  class Solution {
  public:
      int search(int n, vector<int>& a) {
          unordered_map<int, int> mp;
          for(int i = 0; i <= n; i++){
              if(mp.find(a[i]) != mp.end()) //利用哈希表O(1)时间内查找
                  return a[i];
              else
                  mp[a[i]] = 1;
          }
          return 0;
      }
  };

方法三：异或运算

要想在时间复杂度，空间复杂度之内解决这个问题，我们就需要考虑怎么把这个到中重复的唯一一个数字揪出来。

可以考虑异或运算两个法则：、，因此我们只要对这个数字逐一进行累异或运算，相同的两个数会被抵消掉，而我们再与1到n逐一做累异或运算，1到n中非重复的那个数字会被前面没有重复的数字抵消掉，最后只剩下重复的数字。

  class Solution {
  public:
      int search(int n, vector<int>& a) {
          int res = 0; //0异或所有数字等那个数字本身
          for(int i = 0; i <= n; i++){
              if(i != 0){  //非0异或数组元素及1到n数字本身
                  res ^= a[i];
                  res ^= i;
              }else
                  res ^= a[i]; //0只异或数组元素
          }
          return res;
      }
  };

方法四：累加运算

当然除了异或运算，我们发现加法求和也可以得到多出来的那个数字。

我们知道数组中有1到n中的所有数字，多了一个数字x，那我们累加的数组和也比1到n的累加多了数字x。

  class Solution {
  public:
      int search(int n, vector<int>& a) {
          int suma = 0; //记录数组a的和 
          int sumn = (1 + n) * n / 2; //记录1到n的和
          for(int i = 0; i <= n; i++)
              suma += a[i];
          return suma - sumn; //相减
      } 
  };

方法五：快慢双指针

再往深层次考虑，可以把有重复数据的数组看作一个存在环的链表，那么这个环的入口即是要找的重复的数字，因此可以使用快慢指针来找到这个环的入口位置。因为数组长度n+1，数据在[1,n]范围内，因而使用a[a[i]]时，不会越界，且只有一个重复的数，只存在一个环。而且因为下标从0开始，数据中不存在0，所以也不用担心第一个元素会索引到自己，即a[a[i]] = i，不存在这种情况。

慢指针一次性走一步，快指针一次性走两步，相遇则找到了环，环的入口即是重复的元素，再定义一个指针从头开始和慢指针一起一步一步走，相遇的点即是环入口，可以参考一般的环形链表找入口。下图展示怎么将数组视作环形链表：

  class Solution {
  public:
      int search(int n, vector<int>& a) {
          int slow = 0; //定义快慢指针
          int fast = 0;
          slow = a[slow];
          fast = a[a[fast]];
          while(slow != fast){
              slow = a[slow];
              fast = a[a[fast]];
          }
          int find = 0;
          while(find != slow){
              slow = a[slow];
              find = a[find];
          }
          return slow;
      } 
  };

方法六：位置交换法

方法一的排序使用快排看似达到了最快的速度，但是实际上这里如果使用位置交换的排序法，可以更快。我们让1到n中每个数对应在数组中0到n-1的位置，遍历数组a，如果对于每个元素如果位置符合则往后，否则需要将这个元素交换到属于它的位置上去，如果那个位置上已经有和它相同的元素了，则找到重复。

  class Solution {
  public:
      int search(int n, vector<int>& a) {
          int i = 0;
          while(true){
              if(a[i] == i + 1) //符合自己现在的位置
                  i++;
              else if(a[i] == a[a[i] - 1]) //要放的位置上的元素已经有这个元素了，说明找到重复数
                  return a[i];
              else
                  swap(a[i], a[a[i] - 1]); //交换到自己应该去的位置
          }
          return 0;
      } 
  };