LeetCode136/169/75/31/287 算法技巧题核心笔记
目录
一、136. 只出现一次的数字
题目概述
核心理论
解题思路
解法实现（Java）
复杂度分析
重难点分析
同类题拓展
二、169. 多数元素
题目概述
核心理论
解题思路
解法实现（Java）
复杂度分析
重难点分析
同类题拓展
三、75. 颜色分类
题目概述
核心理论
解题思路
解法实现（Java）
复杂度分析
重难点分析
同类题拓展
四、31. 下一个排列
题目概述
核心理论
解题思路
解法实现（Java）
复杂度分析
重难点分析
同类题拓展
五、287. 寻找重复数
题目概述
核心理论
解题思路
解法实现（Java）
复杂度分析
重难点分析
本笔记涵盖 5 道高频算法技巧题的核心解法、理论依据、重难点及拓展，适用于笔试 / 面试复习。
一、136. 只出现一次的数字
题目概述
给定非空整数数组，仅一个元素出现 1 次，其余元素出现 2 次，找出该唯一元素。
核心理论
位运算 异或（^）的三大特性：
- 相同数异或为 0：
a ^ a = 0- 0 与任意数异或为其本身：
0 ^ a = a- 满足交换 / 结合律：
a ^ b ^ c = a ^ c ^ b
解题思路
遍历数组，将所有元素依次异或，出现 2 次的元素会相互抵消为 0，最终结果即为 “只出现 1 次的元素”。
解法实现（Java）
class Solution { public int singleNumber(int[] nums) { int res = 0; for (int num : nums) res ^= num; return res; } }复杂度分析
- 时间复杂度：
O(n)（遍历数组 1 次） - 空间复杂度：
O(1)（仅用一个变量）
重难点分析
- 易错点：容易优先想到 “哈希表统计频率”，但会额外占用
O(n)空间，不符合最优解要求。 - 关键：理解 “异或抵消重复元素” 的本质，避免冗余空间开销。
同类题拓展
- 只出现一次的数字 II（其余元素出现 3 次）
- 只出现一次的数字 III（有 2 个元素各出现 1 次）
二、169. 多数元素
题目概述
给定整数数组，找出出现次数 ** 大于n/2** 的元素（多数元素）。
核心理论
- 摩尔投票法：多数元素的出现次数超过其他所有元素之和，可通过 “抵消” 筛选候选元素。
- 排序特性：排序后数组的中间元素（索引
n/2）必然是多数元素。
解题思路
摩尔投票法：
- 初始化 “候选元素” 和 “计数”。
- 遍历数组：遇相同元素则计数 + 1，不同则 - 1；计数为 0 时更换候选元素。
- 最终候选元素即为多数元素。
解法实现（Java）
class Solution { public int majorityElement(int[] nums) { int candidate = nums[0]; int count = 1; for (int i = 1; i < nums.length; i++) { if (nums[i] == candidate) count++; else { count--; if (count == 0) { candidate = nums[i]; count = 1; } } } return candidate; } }复杂度分析
- 时间复杂度：
O(n) - 空间复杂度：
O(1)
重难点分析
- 易错点：摩尔投票法中 “计数为 0 时更换候选” 的逻辑容易遗漏，导致候选元素错误。
- 关键：理解 “多数元素必然能抵消所有非多数元素” 的核心逻辑，无需统计具体次数。
同类题拓展
- 求众数 II（找出出现次数超过
n/3的元素）
三、75. 颜色分类
题目概述
给定包含0、1、2的数组（代表红、白、蓝），原地排序为0→1→2的顺序，禁止使用库排序函数。
核心理论
三指针法（荷兰国旗问题）：用 3 个指针划分 3 个区域（0 的区域、1 的区域、2 的区域），一次遍历完成排序。
解题思路
- 定义指针：
left：0 的右边界（下一个 0 的位置）right：2 的左边界（下一个 2 的位置）i：当前遍历指针
- 遍历逻辑：
- 遇 0：与
left交换，left++且i++ - 遇 2：与
right交换，right--（i不移动，需检查交换后的元素） - 遇 1：直接
i++
- 遇 0：与
解法实现（Java）
class Solution { public void sortColors(int[] nums) { int left = 0, right = nums.length - 1, i = 0; while (i <= right) { if (nums[i] == 0) { swap(nums, i++, left++); } else if (nums[i] == 2) { swap(nums, i, right--); } else { i++; } } } private void swap(int[] nums, int a, int b) { int temp = nums[a]; nums[a] = nums[b]; nums[b] = temp; } }复杂度分析
- 时间复杂度：
O(n) - 空间复杂度：
O(1)
重难点分析
- 易错点：交换 2 时，
i容易误加 1，导致未检查交换后的元素（可能是 0）。 - 关键：明确三指针的 “区域划分” 作用，避免指针移动逻辑混乱。
同类题拓展
- 移动零（将 0 移到数组末尾）
- 合并两个有序数组（双指针原地合并）
四、31. 下一个排列
题目概述
找出数组的下一个字典序更大的排列；若不存在，则重排为升序（最小排列），要求原地修改、常数空间。
核心理论
字典序 “最小增幅” 规律：
- 找升序断点：从后往前找第一个
nums[i] < nums[i+1]的索引i（i可增大）。 - 找最小增幅数：从后往前找第一个
nums[j] > nums[i]的索引j（保证增幅最小）。 - 调整后续顺序：交换
i、j后，反转i+1后的元素（将降序转为升序，保证后续最小）。
解题思路
- 找升序断点
i：若未找到（数组降序），直接反转数组。 - 若找到
i，找j并交换nums[i]、nums[j]。 - 反转
i+1到末尾的元素。
解法实现（Java）
class Solution { public void nextPermutation(int[] nums) { int n = nums.length, i = n - 2; // 步骤1：找升序断点 while (i >= 0 && nums[i] >= nums[i+1]) i--; // 步骤2：找j并交换 if (i >= 0) { int j = n - 1; while (nums[j] <= nums[i]) j--; swap(nums, i, j); } // 步骤3：反转后续元素 reverse(nums, i+1, n-1); } private void swap(int[] nums, int a, int b) { int temp = nums[a]; nums[a] = nums[b]; nums[b] = temp; } private void reverse(int[] nums, int l, int r) { while (l < r) swap(nums, l++, r--); } }复杂度分析
- 时间复杂度：
O(n) - 空间复杂度：
O(1)
重难点分析
- 易错点：遗漏 “数组完全降序” 的情况（未找到
i时，需反转整个数组）。 - 关键：理解 “最小增幅” 的核心 —— 既让排列变大，又只变大 “一点点”。
同类题拓展
- 全排列（生成所有字典序排列）
- 第 k 个排列（找到第 k 个字典序排列）
五、287. 寻找重复数
题目概述
给定长度为n+1的数组（元素范围[1,n]），有且仅一个重复数，要求不修改数组、常数空间找出该数。
核心理论
快慢指针（弗洛伊德环检测）：将数组转化为 “链表”（索引 = 节点，值 = 下一个节点索引），重复数是环的入口（重复数对应多个前驱节点）。
解题思路
- 找相遇点：慢指针
slow走 1 步，快指针fast走 2 步，两者在环内相遇。 - 找环入口：新指针
ptr从起点出发，slow从相遇点出发，两者同速前进，最终在环入口（重复数）相遇。
解法实现（Java）
class Solution { public int findDuplicate(int[] nums) { // 步骤1：找快慢指针相遇点 int slow = nums[0], fast = nums[nums[0]]; while (slow != fast) { slow = nums[slow]; fast = nums[nums[fast]]; } // 步骤2：找环入口（重复数） int ptr = 0; while (ptr != slow) { ptr = nums[ptr]; slow = nums[slow]; } return ptr; } }复杂度分析
- 时间复杂度：
O(n) - 空间复杂度：
O(1)
重难点分析
- 易错点：难以想到 “数组转链表” 的思路，或不理解 “ptr 与 slow 相遇于环入口” 的数学逻辑。
- 关键：记住结论：从起点和相遇点出发的同速指针，必然在环入口相遇。