今日算法之_14_只出现一次的数字
前言
Github：https://github.com/HealerJean
位运算公式：
对于任意二进制位 x ，有：
异或运算：x ^ 0 = x ， x ^ 1 = ~x
与运算：x & 0 = 0 ， x & 1 = x
1、找出单独出现的数字
给出N个数字。其中仅有一个数字出现过一次，其他数字均出现过两次，找出这个出现且只出现过一次的数字。要求时间和空间复杂度最小。
1.1、解题思路
1.2、算法
1.2.1、算法1：集合
/**
* 算法1：ArrayList
*/
public int singleNumber1(int[] nums) {
List<Integer> list = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
if (list.contains(nums[i])) {
list.remove((Integer) nums[i]);
} else {
list.add(nums[i]);
}
}
return list.get(0);
}
1.2.3、算法2：HashMap
/**
* 算法2：HashMap
*/
public int singleNumber2(int[] nums) {
//map收集每个数字出现的个数
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
map.put(nums[i], map.getOrDefault(nums[i], 0) +1);
}
//找出数量为1的个数
for (Integer key : map.keySet()){
if (map.get(key) == 1){
return key;
}
}
return 0 ;
}
1.2.3、算法3：位运算
/**
* 算法2：官方
*/
public int singleNumber(int[] nums) {
int result = 0;
for (int num : nums) {
result = result ^ num;
}
return result;
}
1.3、测试
@Test
public void test(){
int[] nums = {4,1,2,1,2};
System.out.println(singleNumber1(nums));
System.out.println(singleNumber(nums));
}
2、找出单独出现的数字
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。
说明：你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗
示例 1:
输入: [2,2,3,2]
输出: 3
示例 2:
输入: [0,1,0,1,0,1,99]
输出: 99
2.1、解题思路
2.1.2、算法2解题思路
第一时间应该想到的是找到一种逻辑操作，可以满足 1 * 1 * 1 = 0 且 0 ∗ 1 = 1 ∗ 0 = 1 ，其中 * 为这种新逻辑操作符。根据这个，我们可以想到
1、出现0次为0，出现1次为1，出现2次的值无所谓(因为题目中说明了，肯定是3次)，但是出现3次就又回到0，也就是说，我们一共需要记录3种状态：0次，1次，2次，之后次数都是这三种状态的循环
2、记录两个状态需要的是一位二进制0/1，那么记录三种状态需要的是至少两位二进制，可以是00, 01, 10, 11，这里我们只需要选其中任意三个状态即可（因为到了第三次直接就变成00了），例如：00，01，10，分别代表0次1次2次。
3、那么对于输入数字的每一位二进制位，都可以用这三种状态表示。如果再输入一个数字，对于每一位上，我们的操作可以化为：
新输入的是0（即00），三种状态都维持不变，00→00,01→01,10→10
新输入的是1（即01），00→01,01→10,10→00
设当前状态为 two one ，此时输入二进制位 n 。如下图所示，通过对状态表的情况拆分，可推出 one 的计算方法为：
if two == 0:
if n == 0:
one = one
if n == 1:
one = ~one
if two == 1:
one = 0
引入 异或运算 ，可将以上拆分简化为：
if two == 0:
one = one ^ n
if two == 1:
one = 0
引入 与运算 ，可继续简化为：
one = one ^ n & ~two
同理two
two = two ^ n & ~one
返回值：
以上是对数字的二进制中 “一位” 的分析，而 int 类型的其他 31 位具有相同的运算规则，因此可将以上公式直接套用在 32 位数上。
遍历完所有数字后，此两状态是由 one 来记录的（此两状态下 twos 恒为 00 ），因此返回 ones 即可。
/**
* 算法2：官方
* 异或运算：x ^ 0 = x ， x ^ 1 = ~x
* 与运算： x & 0 = 0 ， x & 1 = x
* 仅当 seen_twice 未变时，改变 seen_once。
* 仅当 seen_once 未变时，改变seen_twice。
* 位掩码 seen_once 仅保留出现一次的数字，不保留出现三次的数字。
*/
public int singleNumber(int[] nums) {
//初始就是00
int seenOnce = 0; //后一位状态
int seenTwice = 0; //前一位状态
for (int num : nums) {
seenOnce = (seenOnce ^ num) & ~seenTwice;
seenTwice = (seenTwice ^ num) & ~seenOnce;
}
//结尾状态为肯定是01，所以取后面的这个
return seenOnce;
}
2.2、算法
2.2.1、算法1：HashMap
/**
* 算法1：HashMap
*/
public int singleNumber1(int[] nums) {
//map收集每个数字出现的个数
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
map.put(nums[i], map.getOrDefault(nums[i], 0) +1);
}
//找出数量为1的个数
for (Integer key : map.keySet()){
if (map.get(key) == 1){
return key;
}
}
return 0 ;
}
2.2.1、算法2：位运算
/**
* 算法2：官方
* 异或运算：x ^ 0 = x ， x ^ 1 = ~x
* 与运算： x & 0 = 0 ， x & 1 = x
* 仅当 seen_twice 未变时，改变 seen_once。
* 仅当 seen_once 未变时，改变seen_twice。
* 位掩码 seen_once 仅保留出现一次的数字，不保留出现三次的数字。
*/
public int singleNumber(int[] nums) {
//初始就是00
int seenOnce = 0; //后一位状态
int seenTwice = 0; //前一位状态
for (int num : nums) {
seenOnce = (seenOnce ^ num) & ~seenTwice;
seenTwice = (seenTwice ^ num) & ~seenOnce;
}
//结尾状态为肯定是01，所以取后面的这个
return seenOnce;
}
2.3、测试
@Test
public void test(){
int[] nums = {4,1,2,1,2};
System.out.println(singleNumber1(nums));
System.out.println(singleNumber(nums));
}
3、找出单独出现的数字
给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。
示例 :
输入: [1,2,1,3,2,5]
输出: [3,5]
3.1、解题思路
3.2、算法
3.2.1、算法1：HashMap
/**
* 算法1：
*/
public int[] singleNumber(int[] nums) {
int[] array = new int[2];
int idx = 0 ;
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
}
for (Integer key : map.keySet()){
if (map.get(key) == 1){
array[idx++] = key;
}
}
return array;
}
3.3、测试
@Test
public void test(){
int[] nums = {4,1,2,1,2};
System.out.println(singleNumber(nums));
}
