数组找出单身狗经典问题

前言

单身狗问题是大厂近几年的一个热门考点,所以我们就一起来探讨一下吧!

摘要

单身狗的问题解法有很多种,今天我带给大家两种经典解法,一、数组比较法,二、异或法,这两种解法我会分开来讲。思路我放在具体板块讲解

一、数组比较法(两只狗)

首先呢,我们要用数组比较,就需要把元素两两比较,当一个数出现两次,使之相减,结果为0的话不是单身狗,反之,这就是我们判断出单身狗的条件,但是如果数组乱序的话相邻元素比较可能为0也可能不为0严重影响判断条件,所以我们使用冒泡排序将数组排序,然后将相邻元素两两比较,碰到“情侣”,就跳过,遇见“单身狗”,则输出,注意数组已经排序,所以相比较单身狗一定在左边(即下标小的元素)

代码解释:首先顶定义一个数组arr,再定义一个num用来存储单身狗元素,冒泡排序函数bubble_sort(如果有小伙伴不了冒泡排序,我会在后续博客中更新,简单说一下思路:讲究n个元素一共排几趟,一趟需要交换机此元素分别由两个for循环控制),单身狗函数思路,相邻两元素相比,如果发现单身狗则存入num数组,使用k来控制循环结束,最总方可找出单身狗6,9

//排序比较法
//void bubble_sort(int arr[], int sz)
//{
// int i = 0;
//
// for (i = 0; i < sz - 1; i++)//一趟
// {
// int j = 0;
// for (j = 0; j < sz - 1 - i; j++)//一趟交换的次数
// {
// if (arr[j] > arr[j + 1])
// {
// int tmp = arr[j];
// arr[j] = arr[j + 1];
// arr[j + 1] = tmp;
// }
// }
// }
//}
//void find(int* arr, int sz,int* num)
//{
// int i = 0;
// int k = 0;
// while (i<sz)
// {
// if ((arr[i] - arr[i + 1]) == 0)
// {
// i = i + 2;
// }
// else
// {
// num[k] = arr[i];//把单身狗放入num数组
// i++;
// k++;
// if (k == 2)
// {
// break;
// }
// }
// }
//}
//int main()
//{
// int arr[] = { 2,1,4,1,2,5,5,4,6,9 };
// int num[2] = { 0 };//存放单身狗元素
// //先使用冒泡排序进行排序
// int sz = sizeof(arr) / sizeof(arr[0]);
// bubble_sort(arr,sz);//排序函数
// find(arr, sz, num);//找单身狗函数
// int i = 0;
// for (i=0;i<2;i++)
// {
// printf("%d ", num[i]);//打印单身狗元素
// }
// return 0;
//}

数组找出单身狗经典问题

二、异或法(两只狗)

在讲解异或法之前我们先介绍一下异或准则:相同为零,不同为1,看图解

数组找出单身狗经典问题

异或法(一只狗)

了解异或后我们先了解一下一只单身狗怎么解,因为相同为零,不同为1,所以将整个数组一起异或,只有出现两次的数字才会异或得0,而得出的最总结果就是单身狗值

数组找出单身狗经典问题

//在一个数组中找出单身狗(一个)问题
void main()
{
int arr[] = { 1,2,3,4,5,1,2,3,4 };
int i = 0;
int dog = 0;
int sz = sizeof(arr) / sizeof(arr[0]);
for (i = 0; i < sz; i++)
{
dog = dog ^ arr[i];//用异或(看成二进制运算相同为0,不同为1)
} //这里将数组的元素全部异或运算(0^1^2^3^4^5^1^2^3^4)最终结果为5
printf("%dn",dog);
return 0;
}

数组找出单身狗经典问题

那么有了一个单身狗的思路,那么有的小伙伴可能就想了:那么两个单身狗问题也就迎刃而解了,还是将全部元素异或,注意大错特错哦,一个单身狗是因为数组中除了它其他元素都是成对出现,所以最终结果为单身狗值,两个单身狗时,其他成对出现的元素异或后还剩下两单身狗异或,最终结果肯定不是单身狗值,所以换个思路想一想,我们只需要将两个单身狗分开(两组),分别将组中元素异或每组得到的值就是分别为单身狗值了,看图解

根据图解我们依据56异或结果二进制位上得1的位数而判断出56二进制在此位肯定不同(在求出具体在哪位不同,用下标拿出来),从而可以将56分为两组,这里就需要引进一个操作符 >> 右移操作符,将两只单身狗异或结果值与1进行逻辑与 (dog >> pos) & 1 方可判断出第几位是1,并将下标值记录在pos中

注:我们的目标是将56分开分位两组分别异或,至于其他出现了两次相同的元素爱分到那组就哪组都行,反正他俩相同的元素异或为0不会有任何影响,最终得到的还是本组的单身狗值

数组找出单身狗经典问题

int main()
{
int arr[] = { 1,2,3,4,5,1,2,3,4,6 };
int i = 0;
int dog = 0;
int sz = sizeof(arr) / sizeof(arr[0]);
for (i = 0; i < sz; i++)
{
dog = dog ^ arr[i];//用异或(看成二进制运算相同为0,不同为1)
} //这里将数组的元素全部异或运算最终结果为两个单身狗异或结果为3
printf("%dn",dog);
int pos = 0;//pos作为记录第几位是1的下标
int dog1 = 0;
int dog2 = 0;
for (pos = 0; pos < 32; pos++)//找出第几位是1
{
if ((dog >> pos) & 1)//根据整个数组的异或结果dog,确定第几位是1,因为我们的主要目的是将单身狗分开
{
break;
}
}
for (i=0;i<sz;i++)
{
if ((arr[i] >> pos) &1)//这里就将数据分组了
{
dog1 = dog1 ^ arr[i];//这里是下标 1 组
}
else
{
dog2 = dog2 ^ arr[i];//这里是下标 0 组
}
}
printf("%d %dn",dog1,dog2);
return 0;
}

数组找出单身狗经典问题

拓展:数组比较法升级版

此方法可以不受单身狗的数量限制,比较灵活

//数组比较法升级版
void bubble_sort(int arr[], int sz)
{
int i = 0;

for (i = 0; i < sz - 1; i++)//一趟
{
int j = 0;
for (j = 0; j < sz - 1 - i; j++)//一趟交换的次数
{
if (arr[j] > arr[j + 1])
{
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
}
}
}
}
void find(int* arr, int sz)
{
int i = 0;
int k = 0;
while (i<sz)
{
if ((arr[i] - arr[i + 1]) == 0)
{
i = i + 2;
}
else
{
printf("%dn",arr[i]);
i++;
}
}
}
int main()
{
int arr[] = { 1,2,3,5,1,2,4,5,6,7,8,4};
//先使用冒泡排序进行排序
int sz = sizeof(arr) / sizeof(arr[0]);
bubble_sort(arr,sz);//排序函数
find(arr, sz);//找单身狗函数
return 0;
}

数组找出单身狗经典问题

留言

欢迎小伙伴们留言评论,如果有错误留言或者私信告诉我,喜欢的话就点赞收藏支持一下吧

发表评论

相关文章