力扣top100(day04-02)--技巧

本文为力扣TOP100刷题笔记

笔者根据数据结构理论加上最近刷题整理了一套 数据结构理论加常用方法以下为该文章：

力扣外传之数据结构（一篇文章搞定数据结构）

136. 只出现一次的数字

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

为什么 XOR 能解决问题？

XOR（^）运算有以下关键特性：

1. 自反性：a ^ a = 0（相同数字异或会抵消）。

2. 恒等性：a ^ 0 = a（任何数字与 0 异或，结果不变）。

3. 交换律和结合律：运算顺序不影响最终结果。

示例：

假设数组是 [2, 1, 4, 1, 2]，计算过程如下：

text

初始值：single = 0
0 ^ 2 = 2
2 ^ 1 = 3
3 ^ 4 = 7
7 ^ 1 = 6
6 ^ 2 = 4

最终结果是 4，它就是唯一出现一次的数字。

为什么能这样计算？

• 所有成对出现的数字都会互相抵消（a ^ a = 0）。

• 最终剩下的就是那个单独的数字（0 ^ a = a）。

时间复杂度 & 空间复杂度

• 时间复杂度：O(n)，只需遍历一次数组。

• 空间复杂度：O(1)，只用了常数空间存储结果。

这种方法非常高效，适用于所有数字出现两次，只有一个数字出现一次的情况。

169. 多数元素

class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length / 2];
    }
}

为什么排序后取中间元素就是多数元素？

• 多数元素的定义：出现次数超过 ⌊n/2⌋，意味着它至少占据数组的一半以上。

• 排序后：由于多数元素的数量超过一半，无论它是数组的最小值还是最大值，排序后它一定会占据中间位置（nums[nums.length / 2]）。

示例：

假设数组是 [3, 2, 3]：

1. 排序后变成 [2, 3, 3]。

2. nums.length / 2 = 1，所以 nums[1] = 3，即多数元素。

另一个例子 [2, 2, 1, 1, 1, 2, 2]：

1. 排序后 [1, 1, 1, 2, 2, 2, 2]。

2. nums.length / 2 = 3，nums[3] = 2，即多数元素。

时间复杂度 & 空间复杂度

• 时间复杂度：O(n log n)，因为 Arrays.sort() 使用的是快速排序或归并排序（平均时间复杂度为 O(n log n)）。

• 空间复杂度：

  • 如果排序是原地进行的（如快速排序），则是 O(1)。

  • 如果排序需要额外空间（如归并排序），则是 O(n)。