欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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大的元素
	}
}