今日算法之_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));
}