只出现一次的数字

难度:

标签:

题目描述

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

你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

示例 1 ：

输入：nums = [2,2,1]
输出：1

示例 2 ：

输入：nums = [4,1,2,1,2]
输出：4

示例 3 ：

输入：nums = [1]
输出：1

提示：

1 <= nums.length <= 3 * 10⁴
-3 * 10⁴ <= nums[i] <= 3 * 10⁴
除了某个元素只出现一次以外，其余每个元素均出现两次。

代码结果

运行时间: 35 ms, 内存: 17.9 MB

// 思路：Java Stream 不太适合直接用于异或操作，但可以通过reduce方法来实现同样的功能。
 
import java.util.Arrays;
 
public class Solution {
    public int singleNumber(int[] nums) {
        return Arrays.stream(nums).reduce(0, (a, b) -> a ^ b);
    }
}

解释

方法:

这个题解使用了异或运算的性质来解决问题。异或运算有以下特点： 1. a ^ 0 = a 2. a ^ a = 0 3. a ^ b ^ a = b 利用这些特点，我们可以通过异或运算来找出只出现一次的数字。将数组中的所有数字进行异或运算，出现两次的数字会被异或为0，而只出现一次的数字和0做异或运算结果还是它本身。最终异或的结果就是只出现一次的数字。

时间复杂度:

O(n)

空间复杂度:

O(1)

代码细节讲解

🦆

为什么使用异或运算来解决这个问题？

▷

异或运算有几个独特的性质，使得它非常适合解决这个问题。首先，任何数和0做异或运算，结果仍然是原数（a ^ 0 = a）。其次，任何数与其自身做异或运算，结果是0（a ^ a = 0）。最后，异或运算满足交换律和结合律，即a ^ b ^ a = b。这些性质使得我们可以通过一次遍历，使用异或运算处理所有数字，最终留下的就是唯一一个只出现一次的数字。出现两次的数字会在异或中彼此抵消变为0。

🦆

在异或操作中，为什么相同的数字异或的结果是0？

▷

异或运算的定义是对二进制位进行运算，相同位得0，不同位得1。因此，当两个相同的数字进行异或运算时，它们的所有二进制位都相同，按位进行异或运算后结果都是0。例如，5的二进制表示是101，5 ^ 5的计算过程是101 ^ 101，每位都是相同的，结果就是000，即0。

🦆

异或运算的顺序是否会影响最终的结果？

▷

不会。异或运算满足交换律和结合律。这意味着无论运算的顺序如何，其结果都是相同的。例如，a ^ b ^ c的结果与c ^ b ^ a或b ^ c ^ a相同。这使得在实际编程中我们无需担心元素的处理顺序，只需要确保每个元素都进行了一次异或运算。

🦆

如果在输入数组中有奇数个重复的数字，这个方法是否仍然有效？

▷

这个方法只对每个数字出现偶数次，而有一个数字出现奇数次（特别是一次）的情况有效。如果有多个数字出现奇数次，或者一个数字出现的次数不是1而是其他奇数，这个方法无法正确找出所有这些只出现奇数次的数字。它只能找到一个数，这个数是数组中所有出现奇数次数字的异或结果。如果只有一个数字出现奇数次，它将正确返回那个数字。

相关问题