1

我已经获得了算法的基本代码，它选择未排序数组中的第 k 个最小元素（或排序，我不确定）。通常，我们会为此使用快速选择，但我们得到了另一个选择，它被标记为“countingselect”作为函数名称。

“计数选择使用类似的方法来计数排序。列表中的项目用作计数数组的索引。然后，从数组的低值端开始，项目计数被累加，直到总数超过所需值。”

// return the kth smallest item
int countingSelect(int items[], int first, int last, int k) {
    int counts[cap];
    for (int c = 0; c < cap; c++) {
        counts[c] = 0;
    }
    for (int i = first; i < last; i++) {
        counts[items[i]] += 1;
    }
    int c = 0;
    while (k >= 0) {
        k -= counts[c++];
    }
    return c-1;
}

我在将其分解为伪代码时遇到了巨大的麻烦，以便我可以准确理解该函数的工作原理。对于我们得到的代码，我的第一个困惑是“cap”的值是什么，它的功能是什么。上限通常是什么值？我没有得到这个信息。

将算法分解为伪代码是理解它的好方法，我请求一些帮助来分解它并逐步执行代码。

先感谢您。

4

2 回答 2

2

我会假设 cap 是列表中的最大数字（因此您可以分配足够的内存）。

计数是每个数字出现在列表中的计数。例如，count[n] 表示列表中 n 的数量。

第一个循环初始化计数值。

第二个循环通过增加计数中的适当位置来调整计数。此循环完成后，counts 是列表中出现的每个数字的计数。例如，count[n] 表示列表中 n 的数量。

最后一位遍历并遍历列表，将前几个索引的元素相加，直到该数字大于 k。然后前面的数字是我们超过 k 的地方，所以我们返回那个数字。

于 2012-06-01T08:27:51.537 回答
2

如果你了解计数排序，这应该很简单。如果不是，那么让我简要介绍一下计数排序的工作原理。

假设您有 10 个数字，范围为 [0, 15]。由于您知道数据的范围，因此您可以检查输入，并标记您看到每个数字的次数。然后迭代计数并按顺序检索数字：

input numbers
counts[0..15] = 0
for i in numbers
    ++counts[numbers[i]]
for i in counts
    counts[i] times
        print i

让我们看一个例子：

numbers: 1 5 3 13 5 2 0 1 14 2

第一个循环创建计数：

(index) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
counts: 1 2 2 1 0 2 0 0 0 0 0  0  0  1  1  0

第二个循环为您提供：

1 times 0
2 times 1
2 times 2
1 time 3
0 times 4
2 times 5
0 times 6
...

那是：

0 1 1 2 2 3 5 5 13 14

您的算法基本相同，只是它不是输出排序列表，而是找到第 k 个最小的项目。

在上面的示例中，您可以看到：

0th smallest numbers is 0
1st and 2nd smallest numbers are 1
3rd and 4th smallest numbers are 2
5th smallest number is 3
6th and 7th smallest numbers are 5
...

如果你仔细观察，你会看到这样的模式：

if      k <= 0 => 0
else if k <= 2 => 1
else if k <= 4 => 2
else if k <= 5 => 3
else if k <= 7 => 5
else if k <= 8 => 13
else if k <= 9 => 14

然而，数字

0 2 4 5 7 8 9

实际上是counts自身的运行总和！

所以，你的算法的底部是一个运行总和，除了它检查总和何时大于k. 当它出现时，之前的数字就是你的答案。请注意，索引counts是数字本身。

int c = 0;
int sum = 0;
while (k >= sum) {
    sum += counts[c++];
}
return c-1;

您的算法试图避免该sum变量，而是从其自身中减去运行总和，k这具有相同的效果。

于 2012-06-01T08:37:01.113 回答