算法导论 Exercises 9.3-6

时间：2023-02-22 23:44:59

Problem Description:

The kth quantiles of an n-element set are the k - 1 order statistics that divide the sorted set into
k equal-sized sets (to within 1). Give an O(n lg k)-time algorithm to list the kth quantiles of a set.

问题描述：

一个集合的第k分位数是指这样k - 1个数：

若将一个大小为n的集合从小到大排好序，这k - 1个数能将这个有序的数列分为k组，并且每组元素的个数相差不超过1。

现给出一个长为n的数组（无序），要求以O(n lg k)的时间复杂度找到其 k 分位数。

比如：

8 4 5 3 2 6 1 7 9  排序后是 1 2 3 4 5 6 7 8 9

其 3 分位数是 3 6，将排序后的数列分成 1 2 3； 4 5 6； 7 8 9 三段，每段元素个数均为3。

2 9 3 4 3 3 9 1 3 8 1 排序后是 1 1 2 3 3 3 3 4 8 9 9

其 4 分位数是 2 3 8，将排序后的数列分成 1 1 2； 3 3 3； 3 4 8； 9 9 四段，每段元素个数分别为 3 3 3 2。

 

解决方案：

首先，我们知道在一个长度为n的无序数组里找到第 i 个数的时间复杂度是O(n)，具体见这篇文章里的算法 ithSmallestLinear 。

所以最直观的方法是调用k次ithSmallestLinear，但这样总时间复杂度是O(kn)而不是题目要求的O(n lg k)。

为了实现从 k 到 lgk 的突破，必然采用分治的方法（我们先假定 n/k 刚好整除）：

0、如果 k == 1 ，return

1、i = k / 2     ……O(1)

    将数组 a 划分成两部分 A 和 B，使得 A 中所有元素不大于 B，且 A 中元素的个数为 tmpSize = (n / k) * i。    ……O(n)

2、在 A 中找第 i 分位数    ……规模减小为 k / 2

3、输出a[tmpSize - 1]    ……O(1)

4、在 B 中找第 k - i 分位数    ……规模减小为 k / 2

由上面的分析，这个算法的时间复杂度满足题设要求O(n lg k)。

 

如果 n/k 不是刚好整除（假设 x = n%k，x != 0），那么我们定义k分位数的分组为：

前 x 组每组的元素个数为⌊n/k⌋ + 1，后 k - x 组每组元素个数为⌊n/k⌋。

比如15个元素分为4组，则每组为 4 4 4 3 个元素。

 

对应的，将tmpSize更改为 (n / k) * i + (n % k < i ? n % k : i)

（ PS：若 k==n ，这实际上是一个O(n lg n)的排序算法。）

 

实现代码：

算法导论 Exercises 9.3-6算法导论 Exercises 9.3-6View Code 
 1 //9.3-6
 2 //list the kth quantiles of a set
 3 void kthQuantiles(int a[], int beg, int end, int k)
 4 {
 5     if (k == 1)
 6     {
 7         return;
 8     }
 9 
10     int len = end - beg + 1;
11     int i = k / 2;
12     int tmpSize = (len / k) * i + (len % k < i ? len % k : i);
13     int pivotLoc = ithSmallestLinear(a, beg, end, beg + tmpSize);
14     pivotLoc = partitionSpecifyPivot(a, beg, end, pivotLoc);
15 
16     kthQuantiles(a, beg, beg + tmpSize - 1, i);
17     std::cout << a[beg + tmpSize - 1] << " ";
18     kthQuantiles(a, beg + tmpSize, end, k - i);
19 }

 

测试代码：

算法导论 Exercises 9.3-6算法导论 Exercises 9.3-6View Code 
 1 #define ARRAY_SIZE 15
 2 #define COUNT 10
 3 
 4 int a[ARRAY_SIZE];
 5 
 6 int main(void)
 7 {
 8     int arraySize = ARRAY_SIZE;
 9     int k = 7;
10     for (int j = 0; j != COUNT; ++j)
11     {
12         //std::cin >> arraySize >> k;
13         randArray(a, arraySize, 1, ARRAY_SIZE * 2);
14         copyArray(a, 0, b, 0, arraySize);
15         quickSort(b, 0, arraySize - 1);
16 
17         //list kth quantiles in O(nlgk)-time
18         kthQuantiles(a, 0, arraySize - 1, k);
19         std::cout << std::endl;
20 
21         //output standard kth quantiles
22         int remainder = arraySize % k;
23         int groupSize = arraySize / k;
24         int currentLoc = -1;
25         for (int i = 1; i != k; ++i)
26         {
27             currentLoc += (groupSize + ((remainder--) > 0 ? 1 : 0));
28             std::cout << b[currentLoc] << " ";
29         }
30         std::cout << std::endl << std::endl;
31     }
32 
33     system("pause");
34     return 0;
35 }

 

文中一些自定义函数的实现见文章“#include”

标签：

相关文章