【LeetCode每日一题】找（一只或者多只）单身狗

💛找（一只或者多只）单身狗题目💛

作业标题

找单身狗

作业内容

一个数组中只有两个数字是出现一次，其他所有数字都出现了两次。

编写一个函数找出这两个只出现一次的数字。

例如：

有数组的元素是：1，2，3，4，5，1，2，3，4，6

只有5和6只出现1次，要找出5和6.

💪 解题思路的分享💪  （一只单身狗）

我们需要用到 ^，也就是异或操作符。

“ ^ ”的异或指的是二进制中，对应的对应二进制位相同时异或为零，相异时异或为一

我们知道，大小相同的数字异或结果一定为0，而0与任何数字进行异或大小不会改变。

那么当单身狗只有一个时，我们可以直接让所有的数据异或在一起，这样最后得出来的就一定是那只单身狗了。

😊题目源码的分享😊

我们来看下面的例子。

#include<stdio.h>
void Single_Dog(int *a, int sz,int *x)
{
  for (int i = 0; i < sz; i++)
  {
  *x ^= a[i];
  }
}
int main()
{
  int x = 0;
  int a[] = { 1,1,2,2,3,3,4,4,5 };
  int sz = sizeof(a) / sizeof(a[0]);
  Single_Dog(a, sz, &x);
  printf("单身狗是%d",x);
  return 0;
}

运行结果如下：

 成功找出单身狗5！

💪 解题思路的分享💪  （多只单身狗）

上面是只有一只单身狗的情况，如果单身狗有两只该怎么办呢？

首先，我们肯定是不能把它们一股脑地异或到一起了，因为单身狗们大小既不相等也大概率不为0，肯定是找不出来的。

不过我们知道，最后异或出来的结果肯定不为0，因为单身狗们的大小肯定不相等。

那我们就找到了解题思路——通过将两只单身狗分组来达到上面只有一只单身狗的情况，然后分别异或到一起。

分组的方法就可以按照异或的结果来，异或相同位0，相异为1，我们就可以找第一个不相等的位置来将单身狗分组，也就是异或结果二进制位里面第一个为1的位置，记录下这个位置。

之后再定义两个变量用来作为两只单身狗，初始化为0。

紧接着遍历数组，当所遍历到的数据右移上面所保存的位置和1按位与的结果为1时，就将它与x异或，反之就和y异或。

这样一通操作下来，x和y就变成了单身狗的样子了！

😊题目源码的分享😊

#include<stdio.h>
void Single_Dog(int* a,int sz,int *m,int *n)
{
  int i, pos = 0, ret = 0;
  for (i = 0; i < sz; i++)
  {
  ret^= a[i];
  }
  for (i = 0; i < 32; i++)
  {
  if (ret >> i == 1)
  {
    pos = i;
    break;
  }
  }
  for (i = 0; i < sz; i++)
  {
  if ((a[i]>>pos&1) == 0)
  {
    *m ^= a[i];
  }
  else if ((a[i] >> pos&1) == 1)
  {
    *n ^= a[i];
  }
  }
}
int main()
{
  int a[] = { 1,1,2,2,3,3,4,4,5,5,6,6,7,8 };
  int sz = sizeof(a) / sizeof(a[0]);
  int m = 0,  n = 0;
  Single_Dog(a, sz, &m, &n);
  printf("%d %d", m, n);
  return 0;
}

👉 本菜鸡&总结 👈

这篇博客旨在总结我自己阶段性的学习，要是能帮助到大家，那可真是三生有幸！😀如果觉得我写的不错的话还请点个赞和关注哦~我会持续输出编程的知识的！🌞🌞🌞

这道题目的方法很难想到，实在不行的话咱们也可以直接采取暴力方式

也就是先排序，在经过一系列操作找出单身狗，不过这个方法有点太复杂了。