专栏首页技术圈在其他数都出现k次的数组中找到只出现一次的数

在其他数都出现k次的数组中找到只出现一次的数

版权声明:本文为博主原创文章,遵循 CC 4.0 by-sa 版权协议,转载请附上原文出处链接和本声明。

本文链接:https://blog.csdn.net/qq_27717921/article/details/77435220

这一类问题可以统称为single-num的问题。主要涉及的知识是位运算。

最初是在牛客网上碰到了k=2和k=3的题目,在左老师的书中看到了一般情况,这里来总结一下。

k=2时

Given an array of integers, every element appears twice except for one. Find that single one.

public class Solution {
    public int singleNumber(int[] A) {
        int result = A[0];
        for(int i=1;i<A.length;i++){
            result = result^A[i];
        }
        return result;
    }
}

k=3

public class Solution {
    public int singleNumber(int[] A) {
        int[] a = new int[32];
        int res = 0;
        for(int i=0;i<32;i++){
            for(int j=0;j<A.length;j++){
                int c =(A[j]>>i)&1;
                a[i] = a[i]+c;
                   
            }
            res=res|(a[i]%3)<<i;
        }
        return res;
    }
}

至于为什么采用异或来求解这个问题,左老师在书中是这样说的。

两个k进制的数a和b,在i位上无进位相加的结果为(a(i)+b(i))%k,如果是k个相同的k进制的数进行无进位I昂家,相加的结果一定是每一位上都是0的k进制数。

因此,我们先设一个32位k进制数组,其实这个数组的大小就为32,并且每一位上都为0,然后遍历数组A,把数组中的一个整数都先转换为k进制,然后在与我们设置的32位的数组进行无进位相加。在遍历结束后,把32位的k进制转换为十进制,k个相同的k进制的无进位相加的结果就是每一位上都是0的k进制,所以那个只出现一次的数则会被剩下来。而k=2的时候就是二进制的异或,当k=3的时候

Single Number的本质,就是用一个数记录每个bit出现的次数,如果一个bit出现两次就归0,这种运算采用二进制底下的位操作^是很自然的。Single Number II中,如果能定义三进制底下的某种位操作,也可以达到相同的效果,Single Number II中想要记录每个bit出现的次数,一个数搞不定就加两个数,用ones来记录只出现过一次的bits,用twos来记录只出现过两次的bits,ones&twos实际上就记录了出现过三次的bits,这时候我们来模拟进行出现3次就抵消为0的操作,抹去ones和twos中都为1的bits

public int singleNumber(int[] A) {
        int ones = 0;//记录只出现过1次的bits
        int twos = 0;//记录只出现过2次的bits
        int threes;
        for(int i = 0; i < A.length; i++){
            int t = A[i];
            twos |= ones&t;//要在更新ones前面更新twos
            ones ^= t;
            threes = ones&twos;//ones和twos中都为1即出现了3次
            ones &= ~threes;//抹去出现了3次的bits
            twos &= ~threes;
        }
        return ones; 
    }

如果对位运算不太熟悉,可以按照左老师写的,将数组A中的每个数都转换为k进制后,在同32位k进制数组累加后转为十进制。

十进制转为k进制

public int[] getKSysNumFormNum(int value,int k){
		int[] res = new int[32];
		int index=0;
		while(value!=0){
			res[index++] = value%k;
			value = value/k;
		}
		return res;
	}

k进制转为十进制

public int getNumFormKSysNum(int[]eo,int k){
		int res = 0;
		for(int i= eo.length-1;i!=-1;i--){
			res = res*k+eo[i];
		}
		return res;
	}

OK

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 动态规划算法举例解析(最大收益和最小损失选择)

    版权声明:本文为博主原创文章,遵循 CC 4.0 by-sa 版权协议,转载请附上原文出处链接和本声明。

    张凝可
  • 面试题目集(一)

    版权声明:本文为博主原创文章,遵循 CC 4.0 by-sa 版权协议,转载请附上原文出处链接和本声明。

    张凝可
  • 基于分治和DP的算法设计

    发现下面的策略都是比较糟糕的,这里提及一下分治和动态规划的区别,动态规划避免了分治方法的重复计算,下面的基本上是用了最朴素的动态规划方案,接下来会用自底向上的方...

    张凝可
  • 1316 文化之旅 2012年NOIP全国联赛普及组

    1316 文化之旅 2012年NOIP全国联赛普及组 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题目描述 ...

    attack
  • Java - 游戏内存外挂

    什么是游戏外挂? 试想场景,在玩游戏时,没有得到良好的游戏体验,加之玩游戏的这位又是偏激之人,此时心生愤怒,但通过自己的游戏技术,又无法得到发泄。所以很无奈,只...

    Melody132
  • 01:数制转换

    01:数制转换 总时间限制: 1000ms 内存限制: 65536kB描述 求任意两个不同进制非负整数的转换(2进制~16进制),所给整数在long所能表达...

    attack
  • 多线程之策略模式

    今天给各位分享一种Java23种设计模式中最常见的设计模式--策略模式。为什么将策略模式和多线程绑在一起呢,不知道各位有没有注意过我们在进行多线程编程的时候,创...

    赵小忠
  • C语言中一些不被熟知的特性

    限定词restricted用于限定一个指针(如名,告诉编译器该指针的内存访问在任何情况下都只能通过该指针进行,其余指向无效.如

    racaljk
  • 浙大版《C语言程序设计(第3版)》题目集 习题5-2 使用函数求奇数和

    其中函数even将根据用户传入的参数n的奇偶性返回相应值:当n为偶数时返回1,否则返回0。函数OddSum负责计算并返回传入的N个整数List[]中所有奇数的和...

    C you again 的博客
  • 迷宫的最短路径

    题意:给定一个大小为N * M的迷宫,迷宫由通道与墙壁组成,每一步可以向邻接的上下左右四格的通道移动。请求出从起点到终点所需要的最下步数。

    用户7727433

扫码关注云+社区

领取腾讯云代金券