跳到主要内容

算法技巧练习

技巧类题目通常不属于单一的算法类别，而是涉及位运算、数学推导、特定的逻辑思维或巧妙的统计方法。这类题目往往需要灵光一现的思路，或者对某些基础概念的深入理解。

掌握这类题目的关键在于：理解底层原理，而不是死记硬背解法。一道技巧题往往有多种解法，理解最优雅的那种解法背后的思想，才能真正掌握这类题目。

136. 只出现一次的数字 (Single Number)​

题目描述​

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

解题思路​

这道题的难点在于要求 O(n) 时间和 O(1) 空间。常规的哈希表计数方法虽然能解决，但需要 O(n) 的空间。

方法：位运算 - 异或​

异或（XOR）运算有两个关键性质：

  1. 任何数与自己异或结果为 0：a ^ a = 0
  2. 任何数与 0 异或结果为自身：a ^ 0 = a
  3. 异或满足交换律和结合律：a ^ b ^ a = (a ^ a) ^ b = 0 ^ b = b

基于这些性质，我们可以将数组中所有元素进行异或运算：

  • 出现两次的元素会相互抵消变成 0
  • 只出现一次的元素会保留下来

例如，数组 [4, 1, 2, 1, 2]：

  • 4 ^ 1 ^ 2 ^ 1 ^ 2
  • = 4 ^ (1 ^ 1) ^ (2 ^ 2)
  • = 4 ^ 0 ^ 0
  • = 4

图解示例​

以 nums = [5, 3, 5, 4, 3] 为例：

初始状态：result = 0

第1步：result = 0 ^ 5 = 5
  二进制：0000 ^ 0101 = 0101

第2步：result = 5 ^ 3 = 6
  二进制：0101 ^ 0011 = 0110

第3步：result = 6 ^ 5 = 3
  二进制：0110 ^ 0101 = 0011
  （注意：5 出现第二次，与之前抵消了一部分）

第4步：result = 3 ^ 4 = 7
  二进制：0011 ^ 0100 = 0111

第5步：result = 7 ^ 3 = 4
  二进制：0111 ^ 0011 = 0100
  （3 出现第二次，完全抵消）

最终结果：4

Java 代码实现​

class Solution {
    public int singleNumber(int[] nums) {
        int result = 0;
        
        // 对所有元素进行异或运算
        for (int num : nums) {
            result ^= num;
        }
        
        return result;
    }
}

复杂度分析​

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

空间复杂度：O(1)，只使用了一个变量存储结果。

异或运算深入理解​

异或运算本质上是"不进位的二进制加法"：

  • 相同位：0 ^ 0 = 0，1 ^ 1 = 0
  • 不同位：0 ^ 1 = 1，1 ^ 0 = 1

这意味着：如果一个数的某一位出现偶数次，该位最终为 0；出现奇数次，该位最终为该位的值。

在这道题中，出现两次的数每个二进制位都出现偶数次（0 或 2 次），只出现一次的数每个二进制位出现奇数次（0 或 1 次）。因此最终结果就是那个只出现一次的数。

相关题目​

169. 多数元素 (Majority Element)​

题目描述​

给定一个大小为 n 的数组 nums，返回其中的多数元素。多数元素是指在数组中出现次数大于 ⌊n/2⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1：

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

示例 2：

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

约束条件：

  • n == nums.length
  • 1 <= n <= 5 * 10^4
  • -10^9 <= nums[i] <= 10^9

解题思路​

多数元素的定义是出现次数超过 n/2 的元素。这意味着多数元素的数量比其他所有元素的总和还多。

方法一：哈希表​

使用哈希表统计每个元素的出现次数，然后找出出现次数超过 n/2 的元素。时间复杂度 O(n)，空间复杂度 O(n)。

方法二：排序​

将数组排序后，多数元素一定出现在位置 n/2。因为多数元素超过一半，无论怎么排列，中间位置必然是多数元素。时间复杂度 O(n log n)，空间复杂度 O(1) 或 O(n)（取决于排序算法）。

方法三：摩尔投票法（Boyer-Moore Voting Algorithm）​

这是最优雅的解法。核心思想是"抵消"：

  • 维护一个候选元素 candidate 和一个计数器 count
  • 遍历数组，如果当前元素等于 candidate，计数器加一
  • 如果不等于，计数器减一
  • 当计数器变为 0 时，更换候选元素为当前元素

为什么这样能找到多数元素？因为多数元素的数量超过一半，即使所有其他元素都来"抵消"它，最后剩下的仍然是多数元素。

图解示例​

以 nums = [2, 2, 1, 1, 1, 2, 2] 为例：

初始状态：candidate = null, count = 0

第1步：num = 2
  count = 0，更换候选
  candidate = 2, count = 1
  
第2步：num = 2
  num == candidate，count++
  candidate = 2, count = 2
  
第3步：num = 1
  num != candidate，count--
  candidate = 2, count = 1
  
第4步：num = 1
  num != candidate，count--
  candidate = 2, count = 0
  
第5步：num = 1
  count = 0，更换候选
  candidate = 1, count = 1
  
第6步：num = 2
  num != candidate，count--
  candidate = 1, count = 0
  
第7步：num = 2
  count = 0，更换候选
  candidate = 2, count = 1

最终结果：2

Java 代码实现​

class Solution {
    public int majorityElement(int[] nums) {
        int candidate = 0;  // 候选元素
        int count = 0;      // 计数器
        
        for (int num : nums) {
            // 当计数器为 0 时，更换候选元素
            if (count == 0) {
                candidate = num;
            }
            
            // 更新计数器
            if (num == candidate) {
                count++;
            } else {
                count--;
            }
        }
        
        // 由于题目保证存在多数元素，所以 candidate 一定是答案
        // 如果不保证，需要二次遍历验证
        return candidate;
    }
}

复杂度分析​

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

空间复杂度：O(1)，只使用了两个变量。

为什么摩尔投票法正确？​

可以这样理解：把多数元素看作"正方"，其他所有元素看作"反方"。

  • 正方的票数严格大于 n/2
  • 反方的票数严格小于 n/2
  • 每次正反抵消一张票，正方必然还有剩余

即使最坏情况（所有反方元素都来抵消正方），正方仍然会获胜。

如果不保证存在多数元素？​

题目保证存在多数元素，所以不需要验证。如果需要验证，可以再遍历一次数组，统计 candidate 的实际出现次数，判断是否超过 n/2。

75. 颜色分类 (Sort Colors)​

题目描述​

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

我们使用整数 0、1 和 2 分别表示红色、白色和蓝色。

必须在不使用库内置的 sort 函数的情况下解决这个问题。

示例 1：

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

示例 2：

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

约束条件：

  • n == nums.length
  • 1 <= n <= 300
  • nums[i] 为 0、1 或 2

解题思路​

这道题也称为"荷兰国旗问题"，要求将数组分成三部分：全 0、全 1、全 2。

方法一：计数排序​

统计 0、1、2 的个数，然后重写数组。需要遍历两次。

方法二：三指针（一次遍历）​

使用三个指针将数组分成四个区域：

  • [0, p0)：全 0
  • [p0, curr)：全 1
  • [curr, p2]：未处理
  • (p2, n-1]：全 2

遍历过程中：

  • 遇到 0：交换到 p0 位置，p0 和 curr 都右移
  • 遇到 1：curr 右移（1 自然留在中间区域）
  • 遇到 2：交换到 p2 位置，p2 左移，curr 不动（因为交换过来的元素还未处理）

图解示例​

以 nums = [2, 0, 2, 1, 1, 0] 为例：

初始状态：
nums = [2, 0, 2, 1, 1, 0]
        ^              ^
      curr=0         p2=5
      p0=0

第1步：nums[0] = 2
  交换 nums[0] 和 nums[5]
  nums = [0, 0, 2, 1, 1, 2]
          ^           ^
        curr=0      p2=4
        p0=0

第2步：nums[0] = 0
  交换 nums[0] 和 nums[0]（自身）
  nums = [0, 0, 2, 1, 1, 2]
             ^
           curr=1
           p0=1

第3步：nums[1] = 0
  交换 nums[1] 和 nums[1]（自身）
  nums = [0, 0, 2, 1, 1, 2]
                ^
              curr=2
              p0=2

第4步：nums[2] = 2
  交换 nums[2] 和 nums[4]
  nums = [0, 0, 1, 1, 2, 2]
                ^
              curr=2
              p2=3

第5步：nums[2] = 1
  curr 右移
  nums = [0, 0, 1, 1, 2, 2]
                   ^
                 curr=3

第6步：nums[3] = 1
  curr 右移
  nums = [0, 0, 1, 1, 2, 2]
                      ^
                    curr=4

curr > p2，结束！

最终结果：[0, 0, 1, 1, 2, 2]

Java 代码实现​

class Solution {
    public void sortColors(int[] nums) {
        // p0: 0 的右边界（不包含）
        // p2: 2 的左边界（不包含）
        // curr: 当前处理位置
        int p0 = 0, curr = 0, p2 = nums.length - 1;
        
        while (curr <= p2) {
            if (nums[curr] == 0) {
                // 交换到 p0 位置
                swap(nums, curr, p0);
                p0++;
                curr++;
            } else if (nums[curr] == 2) {
                // 交换到 p2 位置
                swap(nums, curr, p2);
                p2--;
                // 注意：curr 不增加，因为交换过来的元素还未处理
            } else {
                // nums[curr] == 1，自然留在中间
                curr++;
            }
        }
    }
    
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

复杂度分析​

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

空间复杂度：O(1)，只使用了三个指针变量。

为什么遇到 2 时 curr 不动？​

当遇到 2 时，我们将它与 p2 位置的元素交换。但交换过来的元素可能是 0、1 或 2：

  • 如果是 0：需要继续处理（交换到前面）
  • 如果是 1：可以直接跳过
  • 如果是 2：还需要继续交换

因此，curr 不能动，需要在下一轮继续处理当前位置的新元素。

31. 下一个排列 (Next Permutation)​

题目描述​

整数数组的一个排列就是将其所有成员以序列或线性顺序排列。

整数数组的下一个排列是指其整数的字典序下一个更大的排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即其元素按升序排列）。

给你一个整数数组 nums，找出 nums 的下一个排列。

必须原地修改，只允许使用额外常数空间。

示例 1：

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

示例 2：

输入：nums = [3,2,1]
输出：[1,2,3]
解释：[3,2,1] 是最大的排列，所以返回最小的 [1,2,3]

示例 3：

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

约束条件：

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 100

解题思路​

要找下一个排列，我们需要找到一个比当前排列"大一点"的排列。关键在于"大一点"——找到最小的更大排列。

方法：三步法​

  1. 找到转折点：从右往左找第一个升序对 nums[i] < nums[i+1]。这个 i 就是转折点。如果找不到，说明整个数组是降序的，已经是最大排列。

  2. 找到交换点：在转折点右边，从右往左找第一个比 nums[i] 大的数 nums[j]。

  3. 交换并反转：交换 nums[i] 和 nums[j]，然后将 i+1 到末尾的部分反转。

图解示例​

以 nums = [1, 3, 5, 4, 2] 为例：

第一步：找转折点
从右往左找第一个升序对：
  2 > 4? 否
  4 > 5? 否
  5 > 3? 是！
  
转折点 i = 1，nums[1] = 3

第二步：找交换点
从右往左找第一个比 3 大的数：
  2 > 3? 否
  4 > 3? 是！
  
交换点 j = 3，nums[3] = 4

第三步：交换
交换 nums[1] 和 nums[3]
nums = [1, 4, 5, 3, 2]

第四步：反转
反转 i+1 到末尾，即 [5, 3, 2] → [2, 3, 5]
nums = [1, 4, 2, 3, 5]

最终结果：[1, 4, 2, 3, 5]

为什么这样做是对的？​

理解这个算法的关键在于理解字典序：

  1. 为什么要找转折点？ 转折点右边是降序的，已经是最大的了。要让排列变大，必须在转折点位置换一个更大的数。

  2. 为什么要找最小的更大数？ 找到转折点后，我们想让排列变大，但要变得"尽可能小"。所以要找比转折点大的最小的数。

  3. 为什么要反转？ 交换后，转折点右边仍然是降序的（因为原本就是降序）。要得到最小的排列，需要将这部分变成升序。

Java 代码实现​

class Solution {
    public void nextPermutation(int[] nums) {
        int n = nums.length;
        
        // 第一步：从右往左找转折点
        int i = n - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }
        
        // 如果找到了转折点（不是最大排列）
        if (i >= 0) {
            // 第二步：从右往左找第一个比 nums[i] 大的数
            int j = n - 1;
            while (j > i && nums[j] <= nums[i]) {
                j--;
            }
            
            // 第三步：交换
            swap(nums, i, j);
        }
        
        // 第四步：反转 i+1 到末尾
        // 如果 i == -1，这里就是反转整个数组，得到最小排列
        reverse(nums, i + 1, n - 1);
    }
    
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    
    private void reverse(int[] nums, int left, int right) {
        while (left < right) {
            swap(nums, left, right);
            left++;
            right--;
        }
    }
}

复杂度分析​

时间复杂度：O(n)，最多遍历数组两次（找转折点和找交换点），加上反转操作。

空间复杂度：O(1)，只使用了常数级别的额外空间。

边界情况​

  • 降序数组：如 [3, 2, 1]，找不到转折点（i = -1），直接反转整个数组得到 [1, 2, 3]。
  • 升序数组：如 [1, 2, 3]，转折点是 nums[1] = 2，交换后得到 [1, 3, 2]。
  • 重复元素：如 [1, 1, 5]，转折点是第二个 1，交换后得到 [1, 5, 1]。

287. 寻找重复数 (Find the Duplicate Number)​

题目描述​

给定一个包含 n + 1 个整数的数组 nums，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。

假设 nums 只有一个重复的整数，返回这个重复的数。

你设计的解决方案必须不修改数组 nums 且只用常量级 O(1) 的额外空间。

示例 1：

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

示例 2：

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

约束条件：

  • 1 <= n <= 10^5
  • nums.length == n + 1
  • 1 <= nums[i] <= n
  • nums 中只有一个整数出现两次或多次，其余整数只出现一次

解题思路​

这道题的约束条件非常严格：不能修改数组，只能用 O(1) 空间。这排除了很多常规方法。

方法：快慢指针（Floyd 判圈算法）​

将数组视为一个链表：索引 i 指向 nums[i]。

例如 nums = [1, 3, 4, 2, 2]：

  • 索引 0 指向 nums[0] = 1
  • 索引 1 指向 nums[1] = 3
  • 索引 3 指向 nums[3] = 2
  • 索引 2 指向 nums[2] = 4
  • 索引 4 指向 nums[4] = 2

形成链表：0 → 1 → 3 → 2 → 4 → 2 → 4 → 2 → ...

由于有重复数字，这个链表一定有环。环的入口就是重复的数字。

图解示例​

以 nums = [1, 3, 4, 2, 2] 为例：

第一步：构建链表
索引: 0 → 1 → 3 → 2 → 4 → 2 → 4 → 2 → ...
值:   1   3   2   4   2   4   2   4 ...

形成环：2 → 4 → 2

第二步：快慢指针找相遇点
初始：slow = 0, fast = 0

第1轮：slow = nums[0] = 1, fast = nums[nums[0]] = nums[1] = 3
第2轮：slow = nums[1] = 3, fast = nums[nums[3]] = nums[2] = 4
第3轮：slow = nums[3] = 2, fast = nums[nums[4]] = nums[2] = 4
第4轮：slow = nums[2] = 4, fast = nums[nums[4]] = nums[2] = 4
第5轮：slow = nums[4] = 2, fast = nums[nums[4]] = nums[2] = 4

相遇时：slow 和 fast 都经过节点 2 和 4

第三步：找环入口
ptr = 0, slow = 2

ptr = nums[0] = 1, slow = nums[2] = 4
ptr = nums[1] = 3, slow = nums[4] = 2
ptr = nums[3] = 2, slow = nums[2] = 4

ptr 和 slow 在节点 2 相遇！

重复的数是 2

Java 代码实现​

class Solution {
    public int findDuplicate(int[] nums) {
        // 第一步：快慢指针找相遇点
        int slow = 0, fast = 0;
        
        do {
            slow = nums[slow];          // 慢指针走一步
            fast = nums[nums[fast]];    // 快指针走两步
        } while (slow != fast);
        
        // 第二步：找环入口
        int ptr = 0;
        while (ptr != slow) {
            ptr = nums[ptr];
            slow = nums[slow];
        }
        
        return ptr;
    }
}

复杂度分析​

时间复杂度：O(n)，快慢指针遍历链表的时间。

空间复杂度：O(1)，只使用了几个变量。

为什么这个方法正确？​

这是一道经典的 Floyd 判圈算法应用。关键点：

  1. 数组可以看作链表，因为值范围是 [1, n]，每个值都是有效索引
  2. 有 n+1 个位置但只有 n 个可能的值，所以必有环
  3. 重复的数字意味着多个索引指向同一个值，形成环
  4. 环的入口就是重复的数字

其他方法​

这道题还可以用二分查找解决：

  • 统计数组中小于等于 mid 的元素个数
  • 如果个数大于 mid，说明重复数在 [1, mid] 范围
  • 否则在 [mid+1, n] 范围

时间复杂度 O(n log n)，空间复杂度 O(1)，但不如快慢指针优雅。