leetCode|只出现一次的数字

题目：给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例 1:

• 输入: [2,2,1]
• 输出: 1

示例 2:

• 输入: [4,1,2,1,2]
• 输出: 4

Java代码

class Solution {
    public int singleNumber(int[] nums) {
        int first = nums[0];
        if (nums.length > 1) {
            for (int i = 1; i < nums.length; i++) {
                first = first^nums[i];
            }
        }
        return first;
    }
}

结果

执行用时 :1 ms, 在所有 Java 提交中击败了99.87%的用户
内存消耗 :42.7 MB, 在所有 Java 提交中击败了23.85%的用户

知识点：异或操作

首先异或的特点与位运算与一样，但异或运算不会进位。即bit位相同为0，不同为1。按照这个特点，分析上面代码的执行过程：
数组：[4, 1, 2, 1, 2]
取数组的第一位4:0…000100
第一次异或运算：
0…000100 4
0…000001 1
^------------------
0…000101 5

第二次异或运算
0…000101 5
0…000010 2
^------------------
0…000111 7

第三次异或运算
0…000111 7
0…000001 1
^-----------------
0…000110 6

第四次异或运算
0…000110 6
0…000010 2
^------------------
0…000100 4

最后计算结果为4.

上面异或运算就是消掉数组内相同的元素，出现两次以上的元素经过异或运算后必定为0，而最后留下的就是出现一次的元素。

异或运算的其他使用场景

1.不使用临时空间实现两个数的交换

a = 4, b = 7，不使用临时空间而交换两个值。

a = a ^ b;
b = b ^ a;
a = a ^ b;

a = a ^ b过程
0…0000100 4
0…0000111 7
^----------------
0…0000011 3

b = b ^ a过程
0…0000111 7
0…0000011 3
^----------------
0…0000100 4

a = a ^ b过程
0…0000011 3
0…0000100 4
^----------------
0…0000111 7

2.快速判断两个值是否为0

a = 4, b = 4，快速判断a和b是否相等

return ((a ^ b) == 0 )

3.可快速把数字置为0

a = 10，快速置为0

a = 0 ^ a;

最后

以上就是傲娇柠檬为你收集整理的leetCode|只出现一次的数字的全部内容，希望文章能够帮你解决leetCode|只出现一次的数字所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。