【刷题】只出现一次的数字
链接:
https://www.nowcoder.com/share/jump/2008263481696810321082
https://leetcode.cn/problems/single-number/description/
题目描述
给定一个整数数组,除了某个元素只出现一次以外,其余的每个元素均出现两次,找出只出现一次的那个元素
解法
在使用异或运算解题之前,我们先介绍一下异或运算,并会在使用异或运算解问题之后总结分别利用到了 **异或运算 ** 怎样的性质?
(如果你对异或运算很了解,可以直接跳过 异或运算 的讲解,看其他的解法)
异或运算
- 什么是异或运算?
1.异或运算是位运算 (参与位运算的对象是二进制)
2.异或运算相当于 “无进位相加” ,即 二进制相加不进位 - 定义
两个参与运算的对象,对两对象进行 异或运算 - 运算规则
0^0=0 0^1=1 1^0=1 1^1=0
- 总结
参与运算的两个对象,如果相同则为0,相异则为1 - 性质
任意x与0异或都为x : x^0 = x
任意x与x异或都为0 : x^x = 0 - 用途
1.翻转指定位
例如 : 翻转10100011 的后3位,翻转结果为10100100
10100011 ^ 00000111 = 10100100
- 任何数与0异或值不变
例如 : 10101010 ^ 00000000 = 10101010
- 交换两数
public void swap(int a,int b){ if (a != b){ a ^= b; b ^= a; a ^= b; } }
解法一 : 异或运算
思路 :
遍历数组,对所有的元素进行 异或运算
代码:
public int singleNumber (int[] nums) { int temp = 0; for(int i = 0;i < nums.length;i++){ temp ^= nums[i]; } return temp; }
解释 : 我们在这里都使用到了 关于异或运算 怎么样的性质呢 ?
由于数组中只有一个元素只出现一遍,其余的元素都出现两遍 , 那么我们在对所有元素相异或的时候,会出现这样的现象 x^x = 0, 0^x = x ; 这样之后,当全部元素都相异或之后,temp保存的值就是只出现一遍的元素.
解法二:集合类
Set集合
思路 :
利用Set集合中的contains(K key)方法.
- 遍历数组的同时往Set集合中插入当前元素,插入的前提是集合中不存在该元素,即
- 若该元素在Set中已经存在,则将Set集合中已存在的删除并继续遍历;
- 若该元素在Set中不存在,则顺利插入并继续遍历
- 现在Set集合中就只剩下目标元素temp,通过 迭代Set集合找temp/遍历数组找出Set集合中的temp
代码 :
public int singleNumber(int[] nums) { Set<Integer> set = new HashSet<>(); //遍历数组 for (int i = 0; i < nums.length; i++) { int key = nums[i]; if (set.contains(key)) { set.remove(key); } else { set.add(key); } } //我们这里采用遍历数组获取目标元素 for (int i = 0; i < nums.length; i++) { int key = nums[i]; if (set.contains(key)) { return key; } } return -1; //没有找到返回-1 }
Map集合
思路:
- 遍历数组的同时把数组中的元素插入到Map集合中担任key的角色
- 实时更新存入元素key的value值
我这里采用的是Map集合中的getOrDefault(K key,V value) 方法来做
代码 :
public int singleNumber (int[] nums) { Map<Integer,Integer> map = new HashMap<>(); //遍历数组 for (int i = 0; i < nums.length; i++) { int key = nums[i]; int value = map.getOrDefault(key,0); map.put(key,value+1); } //迭代Map集合,找到value等于1的key for (Map.Entry<Integer,Integer> entrySet: map.entrySet()) { if (entrySet.getValue()==1){ return entrySet.getKey(); } } return -1; }
