?
目录
一，颜色分类
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)。
二，合并区间
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);
}
}
};