算法笔记 随机选择算法

本文将介绍随机选择算法，用于在序列中寻找一个特定位置的元素。

一、求第 K 大数

讨论这样一个问题：如何从一个无序的数组中求出第 K 大的数。

1.先排序后取数

解题思路：

最直接的方法是对数组排序，然后取出第 K 个数即可。但这样的做法需要 o(nlogn) 的时间复杂度。

2.随机选择算法

解题思路：

根据原文，这里的”第 n 大“，应该是从小到大排第 n 位的意思。

原理类似于随机快排。每当对 A[left, right] 执行一次 randPartition 函数后，会有一个元素被确认位置，同时区间被划分成“左小右大”。若“枢轴”下标为 p ，显然“枢轴”此时为序列中第 p-left+1 大的数。

将 p-left+1 与 K 做对比：

  • 若 K > p-left+1 ，说明 K 在右边，需要在右区间中继续划分，寻找第 K - M 大；

    当抛弃右区间时，序列中的 0~M 大都被抛弃，因此序列中剩余元素的大小都应该减去 M

  • 若 K < p-left+1 ，说明 K 在左边边，需要在左区间中继续划分，寻找第 K 大；

  • 若 K == p-left+1 ，说明已经找到， A[K] 即为要找的元素：

解题代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int randPartition(int A[],int low, int high){
	int p = (int)(1.0 * rand() / RAND_MAX * (high - low) + low);
	swap(A[low], A[P]);  //将此随机数指定的数字交换到序列头
	temp = A[low];
	while (low < high){
		while (A[high] >= temp && low < high)    high--;
		A[low] = A[high];
		while (A[low] <= temp && low < high)    low++;
		A[high] = A[low];
	}
	A[low] = temp;
	return low;
}


int randSelect(int A[], int low, int high, int K){
	if (low == high)    return A[low];
	int p = randPartition(A, low, high);  //划分后枢轴位置
	int M = p - low + 1;
	if (K == M)    return A[p];
	else if(K > M)    return randSelect(A, p + 1, high, K - M);
	else    return randSelect(A, left, p - 1, K)
}

虽然这个算法的最坏时间复杂度是 o(n2) ，但是其对任意输入的期望时间复杂度是 o(n) ，是个相当使用且出色的算法。

二、划分集合

给定一个由整数组成的集合，集合中的整数各不相同。要求将其分成两个集合，不得重复，不得遗漏。在“平均分”的前提下，要求它们各自的元素和之差最大，求这个差值。

解题思路：

最直接的思路是将集合从小到大排序，取前一半放入第一个集合，取剩下的放到后一个集合。（这样的话如果总数为奇数，多出来的那个也会被放到后一个集合中。）这样的做法时间复杂度为 o(nlogn) 。

更优做法是利用随机选择算法，先求出原集合中元素的第 n / 2 大，然后根据这个数将集合分为两部分。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int randSelect(int A[], int low, int high, int K);  //找出序列第K大的数

int main(){
	int i;
	int n;
	int sum1, sum2;
	sum1 = sum2 = 0;
	scanf("%d", &n);
	int *A = (int *)calloc(sizeof(int), n);
	for (i = 0; i < n; i++)    scanf("%d", &A[i]);
	randSelect(A, 0, n - 1, n / 2);
	for (i = 0; i < n / 2; i++)    sum1 += A[i];
	for ( ; i < n; i++)    sum2 += A[i];
	printf("%d", sum2 - sum1);
}

​

参考

  • 算法笔记