C语言题目详解——找单身狗

我就是我 2023-09-30 14:43 26阅读 0赞

**目录**

一.题目要求

二.思路分析

三.具体代码

四.运行截图

--------------------

### 一.题目要求 ###

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

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

### 二.思路分析 ###

本题的关键第一在于这两个单身狗数和其他数的区别，第二在于这两个单身狗数之间的区别。

在解决这两个问题之前，我们先来了解一下异或运算符 ( ^ ) 。

> 概念：异或运算符"∧"也称XOR运算符。它的规则是若参加运算的两个二进位同号，则结果为0（假）；异号则为1（真）。即 0∧0＝0，0∧1＝1， 1^0=1，1∧1＝0。
> 
> 简记：相同为0，不相同为1。
> 
> 运算 说明：  
> 0 ^ 0=0，0 ^ 1=1 0异或任何数，其结果=任何数  
> 1 ^ 0=1，1 ^ 1=0 1异或任何数，其结果=任何数取反  
> x ^ x=0 任何数异或自己，等于把自己置0
> 
> 在C语言中（ ^ ）代表了按位异或，即以数字的二进制数为基础，每一位都进行异或运算。

通过以上了解，我们能够知道异或能够将两个数之间每一位数不同置1，相同置0，那么首先我们可以利用异或的特性去遍历整个数组，设置一个初始值e（e的初值为0）依次异或数组中每个元素，最后就能得到两个单身狗数异或的结果，这也就成功的实现了第一个关键问题，即区分出来两个单身狗数和数组中其他数。但到这一步为止我们也只得到了两个单身狗数异或的结果，关于这两个数具体是哪两个数我们还需要再进行一些操作。

第二个问题就是如何分别区分出来这两个单身狗数并表示出来，我们已经得到了两个单身狗数异或的结果，那我们就了解到了这两个数的二进制表示中哪些位是不相同的（这一位为1），那我们可以利用表达式 left = e & (~e+1) 得到e这个数二进制表达中从右往左 第一个出现1的位数（这一位为1，其余位为0）。

> eg：6：110 5：101
> 
> e = 011 left = e & (~e+1) = 001

我们可以设置两个数 num1 = 0 和 num2 = 0 来表示这两个单身狗数，这两个数在这一位肯定是不同的（一个为1，一个为0，具体哪个为 1 哪个为 0 不清楚），那我们可以依据这一点，将整个数组分为两组，可以通过与操作实现（&），其中一组是这一位为1的（ (left & arr\[j\] ) == 1 ），另一组是这一位为0的（ (left & arr\[j\] ) == 0 ）。最后我们通过这两个条件遍历数组，就可以成功分组，由于现在每组只有一个单身狗数，我们再分别对每组中的元素进行依次异或操作，就可以分别得到一个单身狗数。

> 与运算 ( & (按位与）) 是计算机中一种基本的逻辑运算方式，符号表示为“&”，按二进制位进行与运算。
> 
> 运算规则：0&0=0；0&1=0；1&0=0；1&1=1，即：两位同时为“1”，结果才为“1”，否则为“0”。
> 
> 负数按补码形式参加按位与运算。

### 三.具体代码 ###

#include<stdio.h>
    
    void main(){
    	int arr[] = { 1, 4, 6, 3, 5, 2, 1, 3, 4, 2 };
    	int n = sizeof(arr) / sizeof(arr[0]);//求数组长度
    	int e = 0;//0异或任何数都是那个数本身
    	for (int i = 0; i < n; i++){//遍历数组 得出两个单身狗异或的结果（相同的数异或都为0）
    		e ^= arr[i];
    	}
    	int left = e&(~e + 1);
        //记录两个单身狗最左边不相同的那一位 例如：6：110 5：101 那么left=001
    	int num1 = 0, num2 = 0;//两个单身狗
    	for (int j = 0; j < n; j++){
        //将数组中left位是0和1的数分为两组 一个单身狗分别在一组 分别整组异或 分别得到单身狗
    		if ((left&arr[j]) == 0){//left位为0
    			num1 ^= arr[j];
    		}
    		else{//left位为0
    			num2 ^= arr[j];
    		}
    	}
    	printf("%d %d\n", num1, num2);
    }

### 四.运行截图 ###

![5ff51100122e46168fb3284554814d7c.png][]

如有建议或想法 欢迎一起讨论交流~

[5ff51100122e46168fb3284554814d7c.png]: https://img-blog.csdnimg.cn/5ff51100122e46168fb3284554814d7c.png