#yyds干货盘点# 找到数组中唯一成对出现的数字

小蚂蚁

@TOC

题目要求

1 -n 个数，数的范围是：1-> n-1,无序放在n+1个空间的数组中，数组中有一个数重复，找出重复的数

相似题目
之前博主也已经讲解过这类型的题目，也是通过异或解决，大家可以自行查看：
LeetCode-消失的数字
剑指offer-数组中数字出现的次数

例

1 3 2 4 2 放在5个空间的数组中 重复数字为2

方法
和找数组中只有一个数不重复基本一致 ->异或

• 第一步：先将数组全部数进行异或，结果记为：ret
  
• 第二步：将ret和1- >n -1进行异或
  
• 最后异或的结果就算重复的数
  

如：

1 2 3 2 4  此时n = 5 共5个元素
数组所有元素异或：ret = 1^2^3^2^4
异或的结果ret和1-n的数进行异或，此时n=4  ret = 1^2^3^2^4^1^2^3^4 = 2
--重复的数字就是2

代码

Repeat_num(int* arr,int n )
{
  int i = 0;
  int ret = 0;
  //ret和数组元素异或
  for(i = 0;i<n;i++)
  {
    ret ^= arr[i];
  }
  //ret和1 - n-1进行异或
  for(i =1 ;i<= n-1;i++)
  {
    ret^=i;
  }
  return ret;
}
int main()
{
  int arr[10] = {1,2,3,4,5,6,7,8,9,2};
  int ret = Repeat_num(arr,10);
  printf("%d\n",ret);
  return 0;
}

</div>
    
    <div id="asideoffset"></div>