用C语言位运算解决只出现一次的数字I II III

69 阅读 0 评论 46 点赞

我是靠谱客的博主明理水池，最近开发中收集的这篇文章主要介绍用C语言位运算解决只出现一次的数字I II III，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

用C语言解决只出现一次的数字I II III

本章目录

解题需要的C语言基础知识
只出现一次的数字I
只出现一次的数字II
只出现一次的数字III
小编总结

解题所需要的C语言基础知识

hello！从现在开始就进入本题解的正式内容了。首先给大家用图解的方式介绍3个C语言位运算的基本操作符 & | ^
在这里插入图片描述
这些知识对下面的解题都非常重要，一定要熟练掌握，不然等会会有一种“我在哪，我是谁我在干什么”的感觉。

只出现一次的数字I

题目描述

只出现一次的数字
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗？

示例 1:

输入: [2,2,1] 输出: 1
示例 2:

输入: [4,1,2,1,2] 输出: 4

力扣本题链接
解题思路
首先，根据题意，“有不可以额外使用空间这个限定”，看到这里以后要本能的往位运算上面去靠，因为位运算可以不开辟额外空间解决很多问题，然后回看一下刚刚回顾的位运算知识，就知道我们要用到 ^这个操作符了，因为它可以非常简单的消除重复项，剩下只出现一次的数字。
说了这么多，接下来让我们来看看代码的实现

int singleNumber(int* nums, int numsSize){
int ret=0;//0异或任何数都不会印象他的实际值
for(int i=0;i<numsSize;i++)
{
    ret^=nums[i];//所有数异或，重复的消掉，剩下只出现一次的数字
}
return ret;//返回这个数字
}

这只是一个开胃菜，下面正式进入主菜

只出现一次的数字II

题目描述

只出现一次的数字 II 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗？

示例 1:

输入: [2,2,3,2] 输出: 3
``示例 2:

输入: [0,1,0,1,0,1,99] 输出: 99

力扣本题链接
解题思路
如图所示，考虑数字的二进制位形式，出现三次的数字，二进制位各位上的1都是三的倍数，所以求出各位上的1数目，再对3求余，则可求出只出现一次的数字
在这里插入图片描述
那么要怎样求取二进制位各位上1的数目呐，那就要用到&这个操作符了，来看代码实现吧

int singleNumber(int* nums, int numsSize){
    
 int ret=0;
for(int i=0;i<32;++i)//循环遍历二进制位每一位
{
long cnt=0;//不用long，力扣的编译器不通过，不让int类型左移31位，我也不知道
    for(int j=0;j<numsSize;++j) {//将nums数组中每一个数拿出来，二进制位向右移动i位，与1按位与，
    cnt+=(nums[j]>>i)&1;//则可求出二进制位第i位是否为1；
    }
    ret+=(cnt%3)<<i;//将cnt的值模3，求出只出现一次的那个数第i位为1还是为0，再向左移动i位还原，最后相加求出这个数
}
return ret;
}

好了，这个题目就圆满解决了。

只出现一次的数字III

这个题目就很有技巧了题目描述
260. 只出现一次的数字 III 给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。找出只出现一次的那两个元素。你可以按任意顺序返回答案。

进阶：你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？

示例 1：

输入：nums = [1,2,1,3,2,5] 输出：[3,5] 解释：[5, 3] 也是有效的答案。
示例 2：

输入：nums = [-1,0] 输出：[-1,0]
示例 3：

输入：nums = [0,1] 输出：[1,0]

力扣本题链接
解题思路
根据第一题的思路，就知道要全部按位异或，消除重复项。但是两个只出现一次的数也异或在了一起，我们的难点就是怎么将这两个数分离。接下来就用图示法来告诉大家怎样分离两个数
在这里插入图片描述
接下来是代码的实现

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* singleNumber(int* nums, int numsSize, int* returnSize){
int m = 0;
int ret = 0;
for (int i = 0; i < numsSize; i++)
{
	ret ^= nums[i];//将全部数异或
}
while (m < 32)
{
	if ((ret>>m)&1)//找出为1的第m位
		break;
	else
     ++m;
}
int x1 = 0, x2 = 0;//分组
int j=0;
while(j<numsSize)
{
	if ((nums[j]>>m)&1)
		x1 ^= nums[j];//异或出只出现一次的数字
	else
		x2 ^= nums[j];
        j++;
}
int* reRer = (int*)malloc(sizeof(int) * 2);
reRer[0] = x1;
reRer[1] = x2;
*returnSize=2;//根据题意返回长度
return reRer;//返回这两个数
}