wordpress 建筑主题,百度快照seo,佛山市品牌网站建设价格,海会网络建设网站前言#xff1a;
今天在刷题的时候突然看到一道题#xff0c;疑似一位故题。仔细一看#xff0c;欸#xff01;这不是就是单身狗的升级版吗#xff1f;我想那必须再安排一篇#xff0c;不过由于本篇文章与上一篇单身狗文章所涉及的知识点基本相同#xff0c;所以还请大…
前言
今天在刷题的时候突然看到一道题疑似一位故题。仔细一看欸这不是就是单身狗的升级版吗我想那必须再安排一篇不过由于本篇文章与上一篇单身狗文章所涉及的知识点基本相同所以还请大家见谅
我写的开心大家也看个乐呵不过还请单身的人不要介意单纯觉得比较有意思无意冒犯毕竟连小编自己都是单身狗。
后续小编也会尽快更新完指针相关知识点
一、题目
在一场专为情侣们策划的盛宴中竟然有两名单身者悄然混入。宴会的主人感到十分不悦并寻求你的帮助希望你能运用你敏锐的洞察力协助她识破并找出这两名不合规矩的单身者。
无意冒犯只是提供一个题目的背景
例如
有数组的元素是123456123457
只有6和7只出现1次要找出6和7.
二、代码展示无注释的
如果有想先自己思考的可以先看一看这个代码后面也会有解析
#include stdio.h
int find(int num) {int index 0;while ((num 1) 0 index 32) {num 1;index;}return index;
}
void single(int arr[], int sz, int* n1, int* n2) {int Re 0;for (int i 0; i sz; i) {Re ^ arr[i];}int index find(Re);*n1 *n2 0;for (int i 0; i sz; i) {if (((arr[i] index) 1) 1) *n1 ^ arr[i]; else *n2 ^ arr[i];}
int main() {int arr[] {1,2,3,4,5,6,1,2,3,4,5,7};int n1, n2;int sz sizeof(arr) / sizeof(arr[0]);single(arr, sz, n1, n2);printf(两只单身狗分别是%d 和 %d\n, n1, n2);return 0;
}
三、题解思路 1.关于算法我们依然使用的是异或运算因为异或运算相同为0所以将数组中所有的数字进行异或操作最终得到的结果就是那两个只出现一次的数字的异或值。 例如 举个例子 int arr[ ] {1,1,2} 初始re 0 re re ^ 1 1此时re 1 re re ^ 1 1 ^ 1 0;此时re 0 re re ^ 2 0 ^ 2 2;此时re 2所以只出现一次的数字是2 2.找到这个异或结果中为 1 的某一位。根据异或运算不同为1这一位为 1 说明在这一位上那两个只出现一次的数字是不同的。 例如数组{1,1,2} 异或运算1^1^2 2; 0010 2的二进制 异或的结果是0010从右向左找1的位置 0000 0的二进制 0010 2的二进制 0000^0010 0010 (异或运算相同为0不同为1) 我们可以发现0在这一位上的数字是02在这一位上的数字是2说明结果为1的这一位两个只出现一次的数字是不同的。 3.根据这一位将数组中的数字分为两组。一组是这一位为 1 的数字另一组是这一位为 0 的数字。 再对这两组数字分别进行异或操作就可以得到那两个只出现一次的数字。 例如数组为{1,2,3,1,2,4} 第一步将所有数字异或:1 ^ 2 ^ 3 ^ 1 ^ 2 ^ 46 二进制为0110 第二步找到异或结果中为 1 的一位从右往左数第二位为 1 第三步根据这一位将数字分组 这一位为 1 的数字:{3,4}这一位为 0 的数字:{1,2,1,2} 四、函数介绍
1.main函数
int main()
{int arr[] {1,2,3,4,5,6,1,2,3,4,5,7};int n1, n2;int sz sizeof(arr) / sizeof(arr[0]);single(arr, sz, n1, n2);printf(两只单身狗分别是%d 和 %d\n, n1, n2);return 0;
} 数组的输入int arr[] {1,2,3,4,5,6,1,2,3,4,5,7};数组元素个数计算 int sz sizeof(arr) / sizeof(arr[0]);调用函数 single(arr, sz, n1, n2);
2.single函数
void single(int arr[], int sz, int* n1, int* n2) {int Re 0;for (int i 0; i sz; i) {Re ^ arr[i];}int index find(Re);*n1 *n2 0;for (int i 0; i sz; i) {if (((arr[i] index) 1) 1) {*n1 ^ arr[i];}else {*n2 ^ arr[i];}}
}
single函数作用找出数组中两个只出现一次的数字
第一个for循环实现数组中所有元素的异或运算
第二个for循环用于根据索引值将数组分为两组并分别进行异或运算 int index find(Re);将索引值传给find函数
3.find函数
int find(int num) {int index 0;while ((num 1) 0 index 32) {num 1;index;}return index;
} find函数用于找到一个数的二进制表示中从右往左第一个为 1 的位的索引
五代码展示含注释
#include stdio.h
int find(int num)int index 0;while ((num 1) 0 index 32) // 当前二进制位为 0 并且索引小于 32{num 1;//实现二进制中每位检查index;}return index;// 返回第一个结果为 1 的位的索引
}
void single(int arr[], int sz, int* n1, int* n2) int Re 0;// 对数组中所有数字进行异或操作得到两个只出现一次数字的异或结果for (int i 0; i sz; i) {Re ^ arr[i];}int index find(Re);// 找到上述异或结果中第一个为 1 的位的索引*n1 *n2 0;// 根据找到的索引位将数组数字分为两组并分别异或for (int i 0; i sz; i) {if (((arr[i] index) 1) 1) // 判断当前数字在指定索引位是否为 1*n1 ^ arr[i]; else *n2 ^ arr[i]; }
}
int main()
{int arr[] { 1, 2, 3, 2, 1, 4 };int n1, n2;int sz sizeof(arr) / sizeof(arr[0]);//计算数组元素single(arr, sz, n1, n2);//函数调用printf(两只单身狗分别是%d 和 %d\n, n1, n2);return 0;
}
