【刷题-剑指 Offer】 56 - II. 数组中数字出现的次数 II

tech2023-05-27  72

题目

在一个数组 nums 中除一个数字只出现一次之外,其他数字都出现了三次。请找出那个只出现一次的数字。

 

 


方法一:位运算

找到了一个看得懂的答案。

以下解题思路来自剑指Offer,侵删。 解题思路:如果数组中的数字除一个只出现一次之外,其他数字都出现了两次。我们可以如Solution56_1一样用异或位运算(^)解决这个问题。

上述思路不能解决这里的问题,因为三个相同的数字的异或结果还是该数字。尽管我们这里不能应用异或运算,我们还是可以沿用位运算的思路。 如果一个数字出现三次,那么它的二进制表示的每一位(0或者1)也出现三次。如果把所有出现三次的数字的二进制表示的每一位都分别加起来,那么每一位的和都能被3整除。如果某一位的和能被3整除,那么那个只出现一次的数字二进制表示中对应的那一位是0;否则就是1;

上述思路同样适用于数组中一个数字出现一次,其他数字出现奇数次问题(如果是偶数次,直接用异或就可)。

这种解法的时间效率是O(n)。我们需要一个长度为32的辅助数组存储二进制表示的每一位的和。由于数组的长度是固定的,因此空间效率是O(1)。

 

 

public class Solution{ public int singleNumber(int[] nums) {//本算法同样适用于数组nums中存在负数的情况 if(nums.length==0) return -1;//输入数组长度不符合要求,返回-1; int[] bitSum = new int[32];//java int类型有32位,其中首位为符号位 int res=0; for(int num:nums){ int bitMask=1;//需要在这里初始化,不能和res一起初始化 for(int i=31;i>=0;i--){//bitSum[0]为符号位 //这里同样可以通过num的无符号右移>>>来实现,否则带符号右移(>>)左侧会补符号位,对于负数会出错。 //但是不推荐这样做,最好不要修改原数组nums的数据 if((num&bitMask)!=0) bitSum[i]++;//这里判断条件也可以写为(num&bitMask)==bitMask,而不是==1 bitMask=bitMask<<1;//左移没有无符号、带符号的区别,都是在右侧补0 } } for(int i=0;i<32;i++){//这种做法使得本算法同样适用于负数的情况 res=res<<1; res+=bitSum[i]%3;//这两步顺序不能变,否则最后一步会多左移一次 } return res; } }

关于左移和右移:

java的int类型是32位,可以表示 -2^31——2^31。最前面的一位是符号位,正数0,负数1。

eg:0000 0000 0000 0000 0000 0000 0000 0101

1.左移<<

左移1位后 符号位会被保留,数值位左移一位,低位补0,变为:

   0000 0000 0000 0000 0000 0000 0000 1010

2.右移>>

符号位会被保留,数值位左移一位,数值位高位补0,变为:

   0000 0000 0000 0000 0000 0000 0000 0010

可以看到,左移相当于乘以2,右移相当于除以2

3.无符号右移>>>

>>>在右移时会将符号位当做数值位处理,一起右移,高位补0

为了清楚地演示出符号位的变化,以-5为例:

   -5在内存中的存储形式为:1111 1111 1111 1111 1111 1111 1111 1011

   >>>1      后得到:   0111 1111 1111 1111 1111 1111 1111 1101

值为2147483645,很明显,无论从10进制数值,还是从内存中的存储,都能看出,该值比Integer的最大值小2

 

 

 

最新回复(0)