写在前面
快速排序(快速选择)
应用 partition 的快速选择算法
原理
k 的值小于等于左区间的长度-1(即 m-l), 说明不能确定满足条件的值, 继续划分(选择), 否则可以先选出 l 到 m 区间的值, 这段区间的值一定满足条件, 在这种情况下, 如果此时 k 要比 m 到 l 区间的长度+2(即m-l+1) 还大(因为前面记录结果时候记录的数目为 m-l+1), 那就可以划分这个区间了…
题目
215. 数组中的第K个最大元素;(仅取第 k 个)
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
srand(time(0));
int n = nums.size(), idx = n - k;
auto partition = [&](int l, int r) {
swap(nums[rand() % (r - l + 1) + l], nums[r]); // random
int pivot{nums[r]}, i{l};
for (int j{l}; j < r; ++j)
if (nums[j] < pivot) swap(nums[i++], nums[j]);
swap(nums[i], nums[r]);
return i; // pivot 新位置
};
function<int(int, int)> quickSelect = [&](int l, int r) {
int m = partition(l, r);
if (m == idx)
return nums[idx];
else
return m < idx ? quickSelect(m + 1, r) : quickSelect(l, m - 1);
};
return quickSelect(0, n - 1);
}
};
开了随机化之后速度快很多. 算法导论也对此有介绍:
9.2 期望为线性时间的选择算法
上面的解法对于数组部分有序的情况其实是比较慢的…. 力扣增加了新的测试用例. 所以就过不了.
class Solution {
public:
int findKthLargest(vector<int>& arr, int k) {
// srand(time(0));
auto p = [&](int l, int r) {
int x = rand() % (r - l + 1) + l;
swap(arr[l], arr[x]);
int i = l + 1, j = r, pivot = arr[l];
while (1) {
while (i <= j and arr[i] < pivot)
++i;
while (i <= j and arr[j] > pivot)
--j;
if (i >= j)
break;
swap(arr[i], arr[j]);
++i, --j;
}
swap(arr[l], arr[j]);
return j;
};
int n = arr.size();
int l = 0, r = n - 1;
while (1) {
int m = p(l, r);
if (m == n - k) {
return arr[m];
}
if (m > n - k) {
r = m - 1;
} else {
l = m + 1;
}
}
return -1;
}
};
347. 前 K 个高频元素;剑指 Offer 40. 最小的k个数; (用小根堆更普适. 前 k 个)
class Solution {
public:
vector<int> inventoryManagement(vector<int>& arr, int k) {
if (k == 0) {
return {};
}
auto partition = [&](int l, int r) -> int {
int x = arr[r];
int i = l;
for (int j = l; j < r; ++j) {
if (arr[j] < x) {
swap(arr[i++], arr[j]);
}
}
swap(arr[r], arr[i]);
return i;
};
int l = 0, r = arr.size() - 1;
while (1) {
int m = partition(l, r);
if (m == k - 1) {
break;
} else if (m < k - 1) {
l = m + 1;
} else {
r = m - 1;
}
}
return {arr.begin(), arr.begin() + k};
}
};
面试题 17.14. 最小K个数 - 力扣（Leetcode）;
class Solution {
public:
vector<int> smallestK(vector<int>& arr, int k) {
vector<int> ans;
if (k == 0)
return ans;
ans.reserve(k);
auto p = [&](int l, int r) {
swap(arr[rand() % (r - l + 1) + l], arr[r]);
int j{l}, pivot{arr[r]};
for (int i{l}; i < r; ++i) {
if (arr[i] <= pivot) // 递增序
swap(arr[i], arr[j++]);
}
swap(arr[j], arr[r]);
return j;
};
function<void(int, int, int)> f = [&](int l, int r, int k) {
int m = p(l, r);
if (k <= m - l)
f(l, m - 1, k);
else {
for (int i{l}; i <= m; ++i)
ans.emplace_back(arr[i]);
if (k > m - l + 1)
f(m + 1, r, k - (m - l + 1));
}
};
f(0, arr.size() - 1, k);
return ans;
}
};
//一个更好理解的方法
vector<int> lessK(vector<int>& arr, int l, int r, int k) {
auto partition = [&](int l, int r) -> int {
int x = arr[r];
int i = l;
for (int j = l; j < r; ++j) {
if (arr[j] < x) {
swap(arr[i++], arr[j]);
}
}
swap(arr[r], arr[i]);
return i;
};
while (1) {
int m = partition(l, r);
if (m == k - 1) {
break;
} else if (m < k - 1) {
l = m + 1;
} else {
r = m - 1;
}
}
return {arr.begin(), arr.begin() + k};
}
需要注意的点
- 随机化时候取模加上 1, 因为区间为 0 时候(l==r)会导致模 0 Error.
排序
Partition 跟上面一样, 下面用递归实现.
class Solution {
public:
vector<int> sortArray(vector<int>& arr) {
srand(time(0));
auto p = [&](int l, int r) {
int x = rand() % (r - l + 1) + l;
swap(arr[l], arr[x]);
int i = l + 1, j = r, pivot = arr[l];
while (1) {
while (i <= j and arr[i] < pivot)
++i;
while (i <= j and arr[j] > pivot)
--j;
if (i >= j)
break;
swap(arr[i], arr[j]);
++i, --j;
}
swap(arr[l], arr[j]);
return j;
};
int n = arr.size();
auto sort = [&](this auto&& sort, int l, int r) {
if (l >= r) {
return;
}
int m = p(l, r);
sort(l, m - 1);
sort(m + 1, r);
};
sort(0, n - 1);
return arr;
}
};
迭代法的快速排序
class Solution {
public:
vector<int> sortArray(vector<int>& arr) {
srand(time(0));
auto p = [&](int l, int r) {
int x = rand() % (r - l + 1) + l;
swap(arr[l], arr[x]);
int i = l + 1, j = r, pivot = arr[l];
while (1) {
while (i <= j and arr[i] < pivot)
++i;
while (i <= j and arr[j] > pivot)
--j;
if (i >= j)
break;
swap(arr[i], arr[j]);
++i, --j;
}
swap(arr[l], arr[j]);
return j;
};
int n = arr.size();
stack<pair<int, int>> st};
while (!st.empty()) {
auto [l, r] = st.top();
st.pop();
int m = p(l, r);
if (l < m - 1)
st.emplace(l, m - 1);
if (m + 1 < r)
st.emplace(m + 1, r);
}
return arr;
}
};