LeetCode题练习与总结：只出现一次的数字--136

一、题目描述

给你一个 非空 整数数组 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
• 除了某个元素只出现一次以外，其余每个元素均出现两次。

二、解题思路

这个问题可以通过异或（XOR）操作来解决。异或运算有几个特点：

1. 任何数和0做异或运算，结果仍然是原来的数，即 a ⊕ 0 = a。
2. 任何数和其自身做异或运算，结果是0，即 a ⊕ a = 0。
3. 异或运算满足交换律和结合律，即 a ⊕ b ⊕ a = (a ⊕ a) ⊕ b = 0 ⊕ b = b。

根据以上性质，我们可以将数组中的所有元素进行异或运算。成对的元素异或的结果会是0，最终剩下的结果就是只出现一次的那个元素。

三、具体代码

class Solution {
    public int singleNumber(int[] nums) {
        int result = 0;
        for (int num : nums) {
            result ^= num;
        }
        return result;
    }
}

四、时间复杂度和空间复杂度

1. 时间复杂度

时间复杂度是指算法执行的时间随着输入数据量的增加而增长的速度。在这个问题中，我们关注的是算法执行的基本操作次数。

• 初始化操作： int result = 0; 这条语句执行了一次，因此它的复杂度是 O(1)。
• 循环操作： for (int num : nums) { result ^= num; } 这条循环语句会执行 n 次，其中 n 是数组 nums 的长度。循环体中的异或操作 result ^= num 是一个常数时间的操作，因此每次迭代的复杂度是 O(1)。
• 返回操作： return result; 这条语句执行了一次，因此它的复杂度是 O(1)。

总时间复杂度： 将所有操作的时间复杂度相加，我们得到总的时间复杂度是 O(1) + O(n) + O(1)，由于 O(1) 可以忽略不计，因此总的时间复杂度是 O(n)。

2. 空间复杂度

空间复杂度是指算法在执行过程中临时占用存储空间的大小，它是输入数据量的大小的函数。在这个问题中，我们需要考虑算法中使用的额外空间。

• 变量空间： int result; 这条语句定义了一个整数变量 result，它占用的空间是常数大小的，与输入数组 nums 的大小无关。因此，它的空间复杂度是 O(1)。

总空间复杂度： 将所有操作的空间复杂度相加，我们得到总的空间复杂度是 O(1)。

这个算法非常高效，因为它在线性时间内解决了问题，并且只使用了固定空间。

五、总结知识点

1. 异或运算（XOR）：这是代码中的核心概念。异或运算有几个关键特性：任何数与0异或结果为该数本身（a ⊕ 0 = a），任何数与自身异或结果为0（a ⊕ a = 0），异或运算满足交换律和结合律（a ⊕ b ⊕ a = (a ⊕ a) ⊕ b = 0 ⊕ b = b）。这些特性使得异或运算可以用于解决只出现一次的元素问题。

2. 数组的遍历：代码中使用增强型for循环（for (int num : nums)）来遍历数组nums中的每个元素。这是一种简洁的遍历数组元素的方式。

3. 位操作：异或运算是一种位操作，它对两个数的每一位进行比较，如果相同则结果为0，不同则结果为1。位操作是解决许多算法问题的强大工具，尤其是在处理位级操作或优化空间复杂度时。

4. 线性时间复杂度：代码中的循环确保了算法的时间复杂度为O(n)，这意味着算法的运行时间与输入数组的大小成线性关系。

5. 常量空间复杂度：代码中只使用了一个整数变量result来存储最终结果，不随输入数组的大小而变化，因此算法的空间复杂度为O(1)。

6. 算法设计：代码展示了如何利用数学性质来设计高效的算法。通过理解和应用异或运算的特性，可以在线性时间内找到只出现一次的元素，而不需要额外的空间。

以上就是解决这个问题的详细步骤，希望能够为各位提供启发和帮助。