LeetCode 热题100之技巧关卡
1.只出现一次的数字
思路分析1：使用哈希表存储每个数字和该数字出现的次数。遍历数组即可得到每个数字出现的次数，并更新哈希表，最后遍历哈希表，得到只出现一次的数字。
具体实现代码（详解版）：
class Solution {
public:
int singleNumber(vector<int>& nums) {
unordered_map<int,int> mp;
for(int num : nums) mp[num]++;
for(const auto& pair : mp){
if(pair.second == 1){
return pair.first;
}
}
return -1;
}
};
- 时间复杂度：O(n)
- 空间复杂度：O(n)
思路分析2：脑筋急转弯之位运算（异或操作）：这里不需要额外的哈希表，直接利用了异或的性质来完成运算。
- 任何数与 0 异或等于其本身：a ^ 0 = a
- 任何数与自己异或等于 0：a ^ a = 0
- 异或操作满足交换律和结合律：a ^ b ^ a = (a ^ a) ^ b = 0 ^ b = b
- 因此，对于数组中的所有元素，由于出现两次的元素会被抵消（变为 0），最终 res 中只剩下出现一次的元素。
具体实现代码（详解版）：
class Solution {
public:
int singleNumber(vector<int>& nums) {
int res = 0;
for(auto e : nums) res ^= e;//异或操作
return res;
}
};
- 时间复杂度：O(n)
- 空间复杂度：O(1)
2.多数元素
思路分析1：哈希表。
具体实现代码（详解版）：
class Solution {
public:
int majorityElement(vector<int>& nums) {
int n = nums.size();
unordered_map<int,int> mp;
for(int num : nums) mp[num]++;
for(const auto& pair : mp){
if(pair.second > n / 2){
return pair.first;
}
}
return -1;
}
};
- 时间复杂度：O(n)
- 空间复杂度：O(n)
思路分析2：Boyer-Moore 投票算法
- 核心思想：Boyer-Moore 投票算法的核心是**“相互抵消”的策略**：
- 候选多数元素：算法假设存在一个候选多数元素，并通过不断的遍历和计数来验证这个候选多数元素的有效性。
- 计数：算法维护一个计数器 count，用来跟踪候选元素在数组中出现的“净次数”。
- 抵消策略：
- 如果遇到的元素等于当前候选元素，则计数加 1。
- 如果遇到的元素不等于当前候选元素，则计数减 1。
- 当计数减到 0 时，认为当前候选元素不再可能是多数元素（因为支持它的数量被其他元素抵消了），因此换一个新的候选元素并重置计数为 1。
为什么这样操作能找到多数元素？
假设 nums 中的多数元素为 M，它的出现次数超过了数组长度的一半（即大于 ⌊n/2⌋ 次），那么：在计数 count 的增减过程中，多数元素的出现次数无法被其他元素完全抵消掉。
换句话说，虽然其他元素可能抵消掉多数元素的一部分计数，但由于多数元素的数量大于数组中所有其他元素数量的总和，它最终会成为候选元素。
具体实现代码（详解版）：
class Solution {
public:
int majorityElement(vector<int>& nums) {
int can = nums[0];//初始化候选者
int cnt = 0;//计数器初始为0
for(int i = 1; i < nums.size() ; i ++){
if(nums[i] == cnt){//投一票
cnt ++;
}
else{
cnt --;//计数器减一，不等于候选者
if(cnt == 0){//计数器为0，说明当前候选者不够格，淘汰
can = nums[i];//更新候选者
cnt = 1;//计数器归为1
}
}
}
return can;
}
};
3. 颜色分类
思路分析1：不让调用sort，那就手搓快排！Acwing 排序
具体实现代码（详解版）：
class Solution {
public:
void quick_sort(vector<int>& nums,int l ,int r){
if(l >= r) return;
int i = l - 1, j = r + 1,x = nums[l + r >> 1];
while(i < j){
do i ++;while(nums[i] < x);
do j --;while(nums[j] > x);
if(i < j) swap(nums[i],nums[j]);
}
quick_sort(nums,l,j),quick_sort(nums,j + 1, r);
}
void sortColors(vector<int>& nums) {
quick_sort(nums,0,nums.size() - 1);
}
};
思路分析2：三指针（第一次见）：问题实际上是经典的 荷兰国旗问题（Dutch National Flag Problem），可以使用 三指针法（Three-pointer technique） 进行解决。该方法的核心思想是通过三个指针将数组分为三部分：一部分是 0（红色），一部分是 1（白色），一部分是 2（蓝色）。
- 指针定义：
- low：指向当前区间的第一个 1 或 0，用于区分红色区域和白色区域。
- mid：当前扫描指针，扫描所有元素，负责区分白色区域和蓝色区域。
- high：指向当前区间的最后一个 1 或 2，用于区分蓝色区域和白色区域。
- 遍历数组
- 当 nums[mid] == 0 时，将 nums[mid] 和 nums[low] 交换，并增加 low 和 mid 指针。
- 当 nums[mid] == 1 时，直接增加 mid 指针。
- 当 nums[mid] == 2 时，将 nums[mid] 和 nums[high] 交换，并减少 high 指针。此时 mid 指针不增加，因为交换后的 nums[mid] 可能是 0 或 1，需要进一步处理。
- 终止条件：当 mid 超过 high 时，排序完成。
具体实现代码（详解版）：
class Solution {
public:
void sortColors(vector<int>& nums) {
int low = 0, mid = 0, high = nums.size() - 1;
// 当 mid 指针小于或等于 high 指针时，继续排序
while (mid <= high) {
if (nums[mid] == 0) {
// 将 0 移到低位
swap(nums[low], nums[mid]);
low++;
mid++;
} else if (nums[mid] == 1) {
// 1 已经在正确的位置，继续处理下一个
mid++;
} else {
// 将 2 移到高位
swap(nums[mid], nums[high]);
high--;
}
}
}
};
- 时间复杂度：O(n)
- 空间复杂度：O(1)
4.下一个排列
思路分析：先找到第一个降序对的位置，然后这就是我们需要修改替换的位置，用谁替换呢？当然是它右边第一个比它大的数字。这是为了确保我们选择一个 最小的 大于 nums[i] 的数字，这样交换后能保证下一个排列是字典序最小的。
- 从右向左查找第一个降序对：我们从右向左遍历数组，找到第一个满足 nums[i] < nums[i+1] 的位置 i。这个位置的元素是需要改变的元素，因为它决定了排序的次序。
为什么从右向左遍历？
如果我们从右向左找，意味着我们优先改变最后一个不符合递增的数字，这样保证我们修改的是最小的可能的地方，这样能生成下一个较小的、更大的排列。
- 如果我们遍历到头部都没有找到这样的 i，这意味着数组已经是降序排列的，也就是当前排列已经是最大的排列。此时，我们只需将整个数组反转，得到最小的排列（升序排列）。
说明整个数组是降序排列的，比如 [3, 2, 1]。此时，数组已经是最大的排列了。我们将整个数组反转，得到字典序最小的排列。
- 找到大于 nums[i] 的最小元素：如果找到了 i，接下来我们需要在 i+1 到数组末尾的部分中找到一个比 nums[i] 大的最小元素。假设该元素为 nums[j]。
为什么从右边查找 j？
为了确保我们选择一个 最小的 大于 nums[i] 的数字，这样交换后能保证下一个排列是字典序最小的。
- 交换 nums[i] 和 nums[j]：交换 nums[i] 和 nums[j]，这时 nums[i] 会变成一个稍微大的元素，确保字典序的顺序。
- 反转 i+1 到数组末尾的部分：交换后，数组的右半部分并不一定是升序排列的，因此我们需要将它反转成升序，确保得到的排列是下一个字典序排列。
具体实现代码（详解版）：
class Solution {
public:
void nextPermutation(vector<int>& nums) {
int n = nums.size();
// 第一步：从右向左找到第一个降序对 nums[i] < nums[i + 1]
int i = n - 2; // 从倒数第二个元素开始
while (i >= 0 && nums[i] >= nums[i + 1]) {
i--; // 如果 nums[i] >= nums[i + 1]，继续向左移动
}
// 如果找到了降序对
if (i >= 0) {
// 第二步：从右边找第一个比 nums[i] 大的元素 nums[j]
int j = n - 1;
while (nums[j] <= nums[i]) {
j--; // 找到第一个大于 nums[i] 的元素
}
// 第三步：交换 nums[i] 和 nums[j]
swap(nums[i], nums[j]);
}
// 第四步：反转 nums[i+1] 到数组末尾的部分，确保得到的序列是升序
reverse(nums.begin() + i + 1, nums.end());
}
};
- 时间复杂度：O(n)
- 空间复杂度：O(1),所有操作都是在原数组上进行的，没有使用额外的空间。
5.寻找重复数
思路分析1：二分查找
- 利用数组的值的范围
- 数组中的元素范围是 [1, n-1]，且总共有 n 个元素，因此数组中至少有一个元素重复。
- 二分查找
- 通过统计数组中小于等于某个值mid的元素个数来确定重复元素的位置
- 如果小于等等于mid的元素个数超过mid，说明重复的元素在[1,mid]内；
- 否则，重复的元素在[mid + 1,n - 1]区间。
具体实现代码（详解版）：
class Solution {
public:
int findDuplicate(vector<int>& nums) {
int l = 1, r = nums.size() - 1; // 数字范围在 1 到 n-1 之间
while (l < r) {
int mid = l + (r - l) / 2; // 计算中间值
// 统计小于等于 mid 的元素个数
int count = 0;
for (int num : nums) {
if (num <= mid) {
count++;
}
}
// 如果小于等于 mid 的元素个数大于 mid，说明重复的元素在 [l, mid] 区间
if (count > mid) {
r = mid; // 缩小搜索范围
} else {
l = mid + 1; // 否则在 [mid + 1, r] 区间
}
}
return l; // 最终 l 和 r 会指向重复元素
}
};
- 时间复杂度：每次我们都通过二分法将搜索空间减半，并且需要遍历一次数组来统计小于等于 mid 的元素个数。因此时间复杂度为 O(n log n)。
- 空间复杂度：O(1)
思路分析2:快慢指针法
- 快慢指针方法的核心思想是利用 环形链表 的特性来检测重复元素。
数组与链表的映射：我们可以把数组视为一个链表，其中每个元素 nums[i] 表示指向索引 nums[i] 的下一节点。这样，数组的值实际上就成为了链表的节点值。
环的形成：由于数组中有重复元素，必然会形成一个环。例如，如果有重复的数字 x，那么在 x 所在的位置将会有两个指针指向该位置，这样形成了一个环。
快慢指针：慢指针（Tortoise）每次走一步，快指针（Hare）每次走两步；如果链表中存在环，快慢指针必定会相遇。如果它们相遇，那么相遇点就是环的入口，即重复元素所在的位置。
- 初始化：设置慢指针 slow 和快指针 fast，都从数组的第一个元素开始。
- 第一次相遇：快指针每次走两步，慢指针每次走一步。当它们相遇时，说明链表中存在环，且相遇点就是环中的一个位置
- 找到环的入口：将慢指针移动到数组的起始位置，而快指针保持在相遇点，然后两者每次都走一步。当它们再次相遇时，遇到的点就是环的入口，也就是重复的数字。
具体实现代码（详解版）：
class Solution {
public:
int findDuplicate(vector<int>& nums) {
// 第一步：初始化慢指针和快指针
int slow = nums[0], fast = nums[0];
// 第二步：快慢指针在环中相遇
do {
slow = nums[slow]; // 慢指针每次走一步
fast = nums[nums[fast]]; // 快指针每次走两步
} while (slow != fast); // 直到慢指针和快指针相遇
// 第三步：将慢指针移到数组起始位置
slow = nums[0];
// 第四步：慢指针和快指针每次走一步，直到它们再次相遇
while (slow != fast) {
slow = nums[slow]; // 慢指针每次走一步
fast = nums[fast]; // 快指针每次走一步
}
// 返回重复的数字（即相遇点）
return slow;
}
};
- 时间复杂度：O(n)
- 空间复杂度：O(1)