当前位置 博文首页 > 文章内容

    如何利用C语言位运算解决只出现一次的数字

    作者:21344 栏目:未分类 时间:2021-04-07 14:43:32

    解题所需要的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;//返回这两个数
    }
    

    小编总结

    这是我第一次写题解,选了三个相对简单常见的题目,不难,但是也能反应出一种做题的思想。我希望大家不是简单的学会这3个题目,而是学会这种思想去解决更多的题目。同时大家有好的解题方案,也可以在评论区中留言哦,大家互相学习,一起进步。