一，颜色分类
75. 颜色分类 - 力扣（LeetCode）
https://leetcode.cn/problems/sort-colors/?plan=data-structures&plan_progress=zz5yyb3
1，单指针
我们可以考虑对数组进行两次遍历。在第一次遍历中，我们将数组中所有的 0 交换到数组的头部。在第二次遍历中，我们将数组中所有的 1 交换到头部的 0 之后。此时，所有的 2 都出现在数组的尾部，这样我们就完成了排序。
具体地，我们使用一个指针 ptr 表示「头部」的范围，ptr 中存储了一个整数，表示数组 nums 从位置 0 到位置 ptr−1 都属于「头部」。ptr 的初始值为 0，表示还没有数处于「头部」。
在第一次遍历中，我们从左向右遍历整个数组，如果找到了 0，那么就需要将 0 与「头部」位置的元素进行交换，并将「头部」向后扩充一个位置。在遍历结束之后，所有的 0 都被交换到「头部」的范围，并且「头部」只包含 0。
在第二次遍历中，我们从「头部」开始，从左向右遍历整个数组，如果找到了 1，那么就需要将 1 与「头部」位置的元素进行交换，并将「头部」向后扩充一个位置。在遍历结束之后，所有的 1 都被交换到「头部」的范围，并且都在 0 之后，此时 2 只出现在「头部」之外的位置，因此排序完成。
class Solution { public: void sortColors(vector<int>& nums) { int n = nums.size(); int ptr = 0; for (int i = 0; i < n; ++i) { if (nums[i] == 0) { swap(nums[i], nums[ptr]); ++ptr; } } for (int i = ptr; i < n; ++i) { if (nums[i] == 1) { swap(nums[i], nums[ptr]); ++ptr; } } } };
复杂度分析
- 时间复杂度：O(n)，其中 nn 是数组 \textit{nums}nums 的长度。
- 空间复杂度：O(1)。
2，双指针
方法一需要进行两次遍历，那么我们是否可以仅使用一次遍历呢？我们可以额外使用一个指针，即使用两个指针分别用来交换 0 和 1。
具体地，我们用指针 p_0来交换 0，p_1来交换 1，初始值都为 0。当我们从左向右遍历整个数组时：
如果找到了 1，那么将其与 nums[p 1 ] 进行交换，并将 p_1向后移动一个位置，这与方法一是相同的；
如果找到了 0，那么将其与 [p_0]nums[p] 进行交换，并将 p_0向后移动一个位置。这样做是正确的吗？我们可以注意到，因为连续的 0 之后是连续的 1，因此如果我们将 0 与 nums[p 0] 进行交换，那么我们可能会把一个 1 交换出去。当 p_0 < p_1时，我们已经将一些 1 连续地放在头部，此时一定会把一个 1 交换出去，导致答案错误。因此，如果 p_0 < p_1，那么我们需要再将nums[i] 与 nums[p 1] 进行交换，其中 i 是当前遍历到的位置，在进行了第一次交换后，nums[i] 的值为 1，我们需要将这个 1 放到「头部」的末端。在最后，无论是否有 p_0 < p_1，我们需要将 p_0和 p_1均向后移动一个位置，而不是仅将 p_0向后移动一个位置。
class Solution { public: void sortColors(vector<int>& nums) { int n = nums.size(); int p0 = 0, p1 = 0; for (int i = 0; i < n; ++i) { if (nums[i] == 1) { swap(nums[i], nums[p1]); ++p1; } else if (nums[i] == 0) { swap(nums[i], nums[p0]); if (p0 < p1) { swap(nums[i], nums[p1]); } ++p0; ++p1; } } } };
复杂度分析
- 时间复杂度：O(n)，其中 nn 是数组 \textit{nums}nums 的长度。
- 空间复杂度：O(1)。
二，合并区间
56. 合并区间 - 力扣（LeetCode）
https://leetcode.cn/problems/merge-intervals/?plan=data-structures&plan_progress=zz5yyb3
1，排序
思路
如果我们按照区间的左端点排序，那么在排完序的列表中，可以合并的区间一定是连续的。如下图所示，标记为蓝色、黄色和绿色的区间分别可以合并成一个大区间，它们在排完序的列表中是连续的：
#define MAX_LEN 100000 // the amount of buckets class MyHashMap { private: vector<pair<int, int>> map[MAX_LEN]; /** 定义散列函数返回存储数据的下标 */ int getIndex(int key) { return key % MAX_LEN; } /* 查找数据在哈希表中的位置 */ int getPos(int key, int index) { for (int i = 0; i < map[index].size(); ++i) { if (map[index][i].first == key) { return i; } } return -1; } public: MyHashMap() { } /* 插入一个键值对key, value。如果key存在于映射中，则更新其对应的值value */ void put(int key, int value) { int index = getIndex(key); int pos = getPos(key, index); if (pos < 0) { map[index].push_back(make_pair(key, value)); } else { map[index][pos].second = value; } } /* 返回特定的key所映射的value；如果映射中不包含key的映射，返回 -1 */ int get(int key) { int index = getIndex(key); int pos = getPos(key, index); if (pos < 0) { return -1; } else { return map[index][pos].second; } } /** 如果映射中存在key的映射，则移除key和它所对应的value */ void remove(int key) { int index = getIndex(key); int pos = getPos(key, index); if (pos >= 0) { map[index].erase(map[index].begin() + pos); } } };
看题解：
706. 设计哈希映射（详细C++代码基本问题详细） - 设计哈希映射 - 力扣（LeetCode）
https://leetcode.cn/problems/design-hashmap/solution/by-nehzil-bhd2/
