Leetcode题库中，关于数组中元素出现次数的题目有以下几题，重点考察的是对运算符的运用，现在统一归纳，方便后续复习查看。
位运算符简介：
异或运算符（^）: 两个数相同则为0，否则为0。(又称无进位相加)
与运算符（&）：两个数都为1则为1，否则为0。
或运算符（ |）：两个数只要有一个为1则为1，否则就为0。
非运算符（~）：位为0，结果是1，如果位为1，结果是0。
如果位为0，结果是1，如果位为1，结果是0，下面看一个简单例子
左移运算符（<<）：value << num，num 是要向左左移动的位数，丢弃最高位，0补最低位。
右移运算符（>>）：value << num，num 是要向右 移动的位数，符号位不变，左边补上符号位（正数0负数1）。
无符号右移运算符（>>>）：无符号右移规则和右移运算是一样的，只不过忽略了符号位扩展，0补最高位。
根据运算符异或的特性可以推导出：
a ^ a = 0
a ^ 0 = a
a ^ b ^ c = a ^ c ^ b
a & ~a = 0
a & ~0 = a
由易到难：
第一题：136. 只出现一次的数字
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
题解：根据异或运算的规律，由于其满足交换定律，所以a ^ b ^ a = a ^ a ^ b = b，所以针对该题，只需要把所有的元素进行异或运算，最终结果就是要找到元素。
class Solution {
public int singleNumber(int[] nums) {
int ret = 0;
for(int i=0;i<nums.length;i++)
{
ret = ret ^ nums[i];
}
return ret;
}
}
第二题： 137. 只出现一次的数字 II
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。
题解：把数组中的元素当做32位的二进制码处理，每一位非0即1，由于除了一个特殊元素外，其他每个元素均出现了三次，所以所以该位总和为3N或者3N+1，其中1就是那个只出现一次的元素贡献的。
所以只需要数组遍历1到32位，找到每个位置上那个特殊元素贡献的值，就能找到最终的元素。
class Solution {
public int singleNumber(int[] nums) {
int ret = 0;
for(int i=0;i<32;i++)
{
int mask = 1 << i;
int count = 0;
for(int num : nums)
{
//判断该位是否是1
if((num & mask) != 0 )
{
count++;
}
}
//说明想要的那个元素贡献了一位1
if(count % 3 != 0)
{
ret |= mask;
}
}
return ret;
}
}
如果对该题进行拓展，比如其余元素出现2次、3次、4次、5次、k次等等，均可套用该方法，只需要将最后count模k即可。
第三题：面试题56 - I. 数组中数字出现的次数
一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
题解：该题和上面的第一次类似，不同的是数组中存在两个出现一次的数，如果要使用异或运算找出这两个元素的话，就要想办法把这个两个元素划分到不同区域，比如用x、y的第一位不同位来区分。
class Solution {
public int[] singleNumbers(int[] nums) {
//该步骤为了得到m^n,因为相同的元素异或运算=0
int a = 0;
for(int num : nums)
{
a ^= num;
}
//找到m^n 第一位是1，用该标识划分数组
int k = 1;
while((a & k) == 0)
{
k <<= 1;
}
int m =0;
int n=0;
for(int i=0;i<nums.length;i++)
{
if((nums[i] & k) == 0)
{
m ^= nums[i];
}else
{
n ^= nums[i];
}
}
int[] res = {m,n};
return res;
}
}
第四题：645. 错误的集合
集合 S 包含从1到 n 的整数。不幸的是，因为数据错误，导致集合里面某一个元素复制了成了集合里面的另外一个元素的值，导致集合丢失了一个整数并且有一个元素重复。
给定一个数组 nums 代表了集合 S 发生错误后的结果。你的任务是首先寻找到重复出现的整数，再找到丢失的整数，将它们以数组的形式返回。
示例 1:
输入: nums = [1,2,2,4]
输出: [2,3]
题解：对于一个正常的集合S1，S1包含从1到n，而题目中一场的S集合丢失了一个元素并且被其他的元素代替，根据这个思路可以将两个集合异或处理，这样就能得到那两个特殊的元素x^y，比如
S1：a , b, c, d , d
S : a , b, c, d , e
其中元素e被元素d代替,S1 ^ S = (a ^ b ^ c ^ d ^ d) ^ (a ^ b ^ c ^ d ^ e)=(a ^ b ^ c) ^ (a ^ b ^ c ^ d ^ e) = d ^ e
借助第三题中划分元素的思想，可以把S1和S也同步划分，这样S中划分出的区域要比S1划分出的区域中多一个d或者e，这样再进行异或处理便能拿到最终的两个元素。
class Solution {
public int[] findErrorNums(int[] nums) {
//使用位运算符
int x = 0;
int a = 0;
int b = 0;
//该步骤得到x = c ^ d, 其中c:重复的,d:丢失的
for(int num : nums)
{
x ^= num;
}
for(int i=1;i<=nums.length;i++)
{
x ^= i;
}
//找到第一个不为0的位，对c ^ d进行分组
int k = 1;
while((x & k) == 0)
{
k <<= 1;
}
//通过下面的两个循环，拿到最终的a和b
for(int num : nums)
{
if((num & k) == 0)
{
a ^= num;
}else
{
b ^= num;
}
}
for(int i=1;i<=nums.length;i++)
{
if((i & k) == 0)
{
a ^= i;
}else
{
b ^= i;
}
}
//确定重复的元素
for(int i=0;i<nums.length;i++)
{
if(nums[i] == a)
{
return new int[]{a,b};
}
}
return new int[]{b,a};
}
}
网友评论