two pointers 双针法
程序员文章站
2024-02-29 09:41:46
...
顺序表双针
a + b = m
const int maxn =110;
int a[maxn], count = 0, n, m;
int func() {
int i = 0, j = n-1;
while(i >= j) {
if(a[i] + a[j] == m) {
printf("%d + %d = %d\n", a[i], a[j], m);
count++;
i++;
j--;
}
else if (a[i] + a[j] > m) {
j--;
}
else {
i++;
}
}
}
序列合并
// merge a and b into c
void func(int a[], int b[], int c[], int n, int m) {
int i = 0, j = 0, k = 0;
while(i < n && j < m) {
if(a[i] <= b[j]) {
c[k++] = a[i++];
}
else {
c[k++] = b[j++];
}
}
while(i < n) c[k++] = a[i++];
while(j < m) c[k++] = b[j++];
}
归并排序
// a[] 1~n
// 递归
const int maxn = 110;
void merge(int a[], int l1, int r1, int l2, int r2) {
int i = l1, j = l2;
int temp[maxn], k = 0;
while(i < r1 && j < r2) {
if(a[i] < a[j]) temp[k++] = a[i++];
else temp[k++] = a[j++];
}
while(i < r1) temp[k++] = a[i++];
while(j < r2) temp[k++] = a[j++];
for(int i = 0; i < k; ++i) {
a[l1 + i] = temp[i];
}
}
// 非递归
void mergeSort(int a[], int left, int right) {
if(left < right) {
int mid = left + (right - left) / 2;
mergeSort(a, left, mid);
mergeSort(mid + 1, right);
merge(a, left, mid, mid + 1, right);
}
}
void mergeSort(int a[]) {
for(int step = 2; step/2 <= n; step *= 2) {
for(int i = 1; i <= n; i += step) {
int mid = i + step / 2 - 1;
if(mid + 1 <= n) { // 右区间仍有元素
merge(a, i, mid, mid + 1, min(i + step - 1, n));
}
}
}
}
// 偷懒直接sort
void mergeSort(int a[]) {
for(int step = 2; step/2 <= n; step *= 2) {
for(int i = 1; i <= n; i += step) {
sort(a + i, a + min(i + step, n + 1)); // sort左闭右开
}
}
}
快速排序
// quick sort
int partition(int a[], int left, int right) {
int t = a[left];
while(left < right) {
while(left < right && a[right] > t) right--;
a[left] = a[right];
while(left < right && a[left] <= t) left ++;
a[right] = a[left];
}
a[left] = t;
return left;
}
void quickSort(int a[], int left, int right) {
if(left < right) {
int pos = position(a, left, right);
quickSort(a,left, pos - 1);
quickSort(a, pos + 1, right);
}
}
// 添加 随机数
#include <cstdio>
#include <cstdlib>
#include <time.h>
int main() {
srand((unsigned)time(NULL)); // 生成随机数种子
// ...
return 0;
}
int randPartition(int a[], int left, int right) {
int p = (round(1.0 * rand() / RAND_MAX * (right - left) + left));
swap(a[p], a[left]);
// 下同partition
int t = a[left];
while(left < right) {
while(left < right && a[right] > t) right--;
a[left] = a[right];
while(left < right && a[left] <= t) left++;
a[right] = a[left];
}
a[left] = t;
return left;
}
随机选择算法
求序列中第K大的元素
int randSelection(int a[], int left, int right, int k) {
if(left == right) return a[left];
int p = randPartition(a, left, right);
int rank = p - left + 1; // p位置元素的排名
if(rank == p) return a[rank];
else if (rank < p) { // p位置元素排名在k前, 从后半部分继续寻找
return randSelection(a, p + 1, right, k - m); // 后半部分寻找第K-rank大的元素
}
else {
return randSelection(a, left, p - 1, k); // 前半部分寻找第K大的元素
}
}
上一篇: java 解析压缩文件-gzip
下一篇: Java使用GZIP进行压缩和解压
推荐阅读
-
two pointers 双针法
-
Move Zeroes——Two Pointers
-
two pointers
-
2021暑假Leetcode刷题——Two Pointers(2)
-
extjs two tree 动态双树代码 效果图 博客分类: js EXTJSP
-
extjs two tree 动态双树代码 效果图 博客分类: js EXTJSP
-
leetcode之哈希法与双指针法求多数之和
-
算法学习(3)-经典的双指针法则
-
LeetCode C++ 454. 4Sum II【Hash Table/Sort/Two Pointers/Binary Search】
-
双指针法-删除数组中的重复元素以及奇偶排序