「剑指Offer」Day22:位运算(中等)
剑指 Offer 56 - I. 数组中数字出现的次数
题目描述
一个整型数组nums里除两个数字之外,其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n),空间复杂度是O(1)。
输入:nums = [1,2,10,4,1,4,3,3] 输出:[2,10] 或 [10,2]
🔗题目链接:https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/
思路
本题有很多方法可以解决,但根据题意重复的数字都出现了两次,且本题的空间复杂度要求是O(1),所以使用位运算最为合适。
我们知道两个相同的数异或等于0,任意一个数与0异或等于该数,即,若数组中只有一个只出现一次的数字,其它数字都出现了两次,就可以使用异或运算得到只出现一次的数字,但本题有所不同,有两个只出现一次的数字,使用异或得到的是两数异或的结果,但我们可以从该结果入手,两数只出现一次且不同,则它们的二进制形式至少有一位是不同的,因此可以根据该二进制位将数组分为分别包含这两数的子数组,遍历异或即可分别提取出子数组中的结果数。
如数组[4,1,6,4],遍历异或得到 0001 异或 0110 = 0111,取出最低位的1为0001, 则根据该位将数组分为(x & 0001)== 0和(x & 0001)== 1的两组,即[4,6,4]和[1], 分别再进行异或即可得到子数组的结果值
代码实现
class Solution { public int[] singleNumbers(int[] nums) { int m = 0; int x1 = 0; int x2 = 0; for(int num : nums){ //两个只出现一次的数字的异或结果 m ^= num; } int n = m & (-m); //m最低位的1 for(int num : nums){ //分组异或 if((num & n) != 0){ x1 ^= num; }else{ x2 ^= num; } } return new int[]{x1, x2}; } }
剑指 Offer 56 - II. 数组中数字出现的次数 II
题目描述
在一个数组nums中除一个数字只出现一次之外,其他数字都出现了三次。请找出那个只出现一次的数字。
输入:nums = [9,1,7,9,7,9,7] 输出:1🔗题目链接:https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-ii-lcof/
思路
代码实现
class Solution { public int singleNumber(int[] nums) { int[] counts = new int[32]; //记录所有数字各二进制位的1的出现次数 for(int num : nums){ for(int j = 0; j < 32; j++){ counts[j] += num & 1; num >>>= 1; } } //通过左移操作和或运算,将counts数组中各二进位的值恢复到数字res上 int res = 0; for(int i = 0; i < 32; i++) { res <<= 1; res |= counts[31 - i] % 3; } return res; } }