你是真的“C”——找单身狗~

😎博客昵称：博客小梦

😊最喜欢的座右铭：全神贯注的上吧！！！

😊作者简介：一名热爱C/C++，算法等技术、喜爱运动、热爱K歌、敢于追梦的小博主！

😘博主小留言：哈喽！😄各位CSDN的uu们，我是你的博客好友小梦，希望我的文章可以给您带来一定的帮助，话不多说，文章推上！欢迎大家在评论区唠嗑指正，觉得好的话别忘了一键三连哦！😘

前言🙌

   哈喽各位友友们😊，我今天又学到了很多有趣的知识，现在迫不及待的想和大家分享一下！😘我仅已此文，和大家分享你是真的“C”——找单身狗~ 都是精华内容，可不要错过哟！！！😍😍😍

初阶——找单身狗问题：

在一组数组中，有一只“单身狗”（该数字只出现一次），其他的数字都有一个和自己相同的数字。

其实解答此题有许多的方法，例如直接将数组进行一个排序，然后定义两个指针，然后寻找到单身狗。这里介绍的是用异或运算来解答这道题目，效率也比较高。

异或运算的规律：

• 1.相同为零，相异为1；
• 2.任何数和0异或等于其本身
• 3.两个相同的数异或为0.

解题源码分享： 😘

#include <stdio.h>
int main()
{
  int single_dog[] = { 1,2,3,4,1,2,3,4,5 };
  int sz = sizeof(single_dog) / sizeof(int);
  int i = 0;
  int sin_dog = 0;
  for (i = 0; i < sz; i++)
  {
    sin_dog^= single_dog[i];
  }
  printf("%d", sin_dog);
  return 0;
}

程序输出结果验证： 😊

进阶——找单身狗问题：

在一组数组中，有两只“单身狗”（有两个数字只出现一次），其他的数字都有一个和自己相同的数字。

• 1.这道题明显比初阶找单身狗的问题难度明显上升，但是解法也很相似。
• 2.那我们可不可以将这个问题转换成初阶单身狗问题呢？显然是可以的。这道题的核心就是进行一个分组，让两只单身狗分别在不同的组里面。这里举例说明一下两只单身狗为4和5。
• 3.我们知道 4 的 二进制为：0100 。 5 的二进制为： 0101。可以发现 4 和 5 的最低二进制位上的数字不同。因此，这个可以作为分组的条件。
• 4.然后依次对每一个组的数字进行一个异或，最终得到每一组的单身狗。

解题源码分享： 😘

#include <stdio.h>
int main()
{
  int single_dog[] = {1,2,3,4,1,2,3,5};
  int sz = sizeof(single_dog) / sizeof(int);
  int i = 0;
  int dog1 = 0;
  int dog2 = 0;
  for (i = 0; i < sz; i++)
  {
    //分组：
    // 4 : 0100  5: 0101 
    if ((single_dog[i] & 1) == 1)
    {
      dog1 ^= single_dog[i];
    }
    else if((single_dog[i] & 1) == 0)
    {
      dog2 ^= single_dog[i];
    }
  }
  printf("%d %d", dog1, dog2);
  return 0;
}

程序输出结果验证： 😊

总结撒花💞

   本篇文章旨在分享你是真的“C”——找单身狗。希望大家通过阅读此文有所收获😘如果我写的有什么不好之处，请在文章下方给出你宝贵的意见😊。如果觉得我写的好的话请点个赞赞和关注哦~😘😘😘