地址
难度
简单
题目
给你一个非空整数数组nums，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。
示例 1 ：
输入：nums = [2,2,1]
输出：1
示例 2 ：
输入：nums = [4,1,2,1,2]
输出：4
示例 3 ：
输入：nums = [1]
输出：1
提示：
- 1 <= nums.length <= 3 * 10^4
- -3 * 10^4 <= nums[i] <= 3 * 10^4
- 除了某个元素只出现一次以外，其余每个元素均出现两次。
思路
- HashMap
首先想到用 HashMap 的这个方法，题目要求不是让求次数嘛，那直接遍历数组将每个数字和其出现的次数存到哈希表里就可以了，然后再从哈希表里找出出现一次的那个数返回即可。
class Solution {
public int singleNumber(int[] nums) {
//特殊情况
if (nums.length == 1) {
return nums[0];
}
//HashMap
HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
//将其存入哈希表中，含义为，若该元素不存在则存入表中，并计数为1，若已经存在获取次数并加1.
for (int x : nums) {
map.put(x , map.getOrDefault(x,0) + 1);
}
//遍历出出现次数为1的情况
for (int y : map.keySet()) {
if(map.get(y) == 1){
return y;
}
}
return 0;
}
}
- 排序搜索法
首先对数组进行排序，然后遍历数组，因为数组中其他数字都出现两次，只有目标值出现一次，所以让的指针每次跳两步，当发现当前值和前一位不一样的情况时，返回前一位即可，当然需要考虑这种情况，当的目标值出现在数组最后一位的情况，所以当数组遍历结束后没有返回值，则需要返回数组最后一位。
class Solution {
public int singleNumber(int[] nums) {
if (nums.length == 1){
return nums[0];
}
//排序
Arrays.sort(nums);
for (int i = 1; i < nums.length-1; i+=2){
if (nums[i] == nums[i-1]){
continue;
}else{
return nums[i-1];
}
}
return nums[nums.length-1];
}
}
- HashSet
利用 HashSet 来完成。它是基于 HashMap 来实现的，是一个不允许有重复元素的集合。那么在这个题解中，它起到什么作用呢？解题思路如下，依次遍历元素并与 HashSet 内的元素进行比较，如果 HashSet 内没有该元素（说明该元素第一次出现）则存入，若是 HashSet 已经存在该元素(第二次出现)，则将其从 HashSet 中去除，并继续遍历下一个元素。最后 HashSet 内剩下的则为我们的目标数。
class Solution {
public int singleNumber(int[] nums) {
if (nums.length == 1){
return nums[0];
}
HashSet<Integer> set = new HashSet<>();
//循环遍历
for (int x : nums){
//已经存在，则去除
if(set.contains(x)){
set.remove(x);
}
//否则存入
else{
set.add(x);
}
}
//返回仅剩的一个元素
return set.iterator().next();
}
}
- 栈
首先将其排序，然后遍历数组，如果栈为空则将当前元素压入栈，如果栈不为空，若当前元素和栈顶元素相同则出栈，继续遍历下一元素，如果当前元素和栈顶元素不同的话，则说明栈顶元素是只出现一次的元素，将其返回即可。
class Solution {
public int singleNumber(int[] nums) {
if (nums.length == 1) {
return nums[0];
}
Arrays.sort(nums);
Stack<Integer> stack = new Stack<>();
for (int x : nums){
if (stack.isEmpty()) {
stack.push(x);
continue;
}
//不同时直接跳出
if (stack.peek() != x) {
break;
}
//相同时出栈
stack.pop();
}
return stack.peek();
}
}
- 求和法
借助HashSet，具体思路如下，通过 HashSet 保存数组内的元素，然后进行求和（setsum），那么得到的这个和则为去除掉重复元素的和，也可以得到所有元素和（numsum）。因为其他元素都出现两次，仅有一个元素出现一次，那通过 setsum * 2 - numsum 得到的元素则为出现一次的数。
class Solution {
public int singleNumber(int[] nums) {
if (nums.length == 1){
return nums[0];
}
HashSet<Integer> set = new HashSet<>();
int setsum = 0;
int numsum = 0;
for (int x : nums) {
//所有元素的和
numsum += x;
if (!set.contains(x)) {
//HashSet内元素的和
setsum += x;
}
set.add(x);
}
//返回值
return setsum * 2 - numsum;
}
}
- 位运算
主要是借助 位运算符 ^ 按位异或，先来了解一下这个位运算符。
按位异或(XOR)运算符“^”是双目运算符。
其功能是参与运算的两数各对应的二进位相异或，当两对应的二进位相异时，结果为1。相同时为0。
任何数和0异或，仍为本身：a⊕0 = a
任何数和本身异或，为0：a⊕a = 0
异或运算满足交换律和结合律：a⊕b⊕a = (a⊕a)⊕b = 0⊕b = b
通过上面的例子了解了异或运算，对应位相异时得 1，相同时得 0，那么某个数跟本身异或时，因为对应位都相同所以结果为 0 ， 然后异或又满足交换律和结合律。
class Solution {
public int singleNumber(int[] nums) {
int result = 0;
for(int i=0;i<nums.length;i++){
result ^= nums[i];
}
return result;
}
}
题解出处：