1

我是一名 compsci 学生，我在分析与设计 II 课上收到以下问题：

无序集合的中位数是这样一个元素，即小于中位数的元素数量在大于中位数的元素之一内，假设没有关系。

(a) 编写一个算法，找出 3 个不同值 a、b、c 的中值。

(b) 确定您的算法在平均情况和最坏情况下进行的比较次数。

从我搜索和学习的一点点来看，这似乎被称为找到未排序数组的第k个元素，或者找到中位数的中位数？

但是，我们还没有学会快速排序，而且我能找到的一切似乎都比这里要求我的要复杂得多。也就是说，我不完全确定我理解这个问题中提出的定义。此外，找到 3 个不同值 a、b、c 的中位数是否意味着找到一组大小为 3 的中位数？

我不一定要寻找答案。只是简单的解释或澄清。谢谢。

尝试#1

(a) 按照 templatetypedef 的建议，我想出了这个简单的算法来解决这个问题：

medianOf(int a, int b, int c)
    if a < b
        if a > c
            return a
    else //a > b
        if a < c
            return a    

    if b < c
        if b > a
            return b
    else //b > c
        if b < a
            return b

    if c < a
        if c > b
            return c
    else //c > a
        if c < b
            return c

我知道这非常幼稚和丑陋，但我想不出更好的解决方案，而且这已经花费了我太多时间。

(b) 似乎最好的情况是 c < a < b 进行 2 次比较，最坏的情况是 a < c < b 进行 9 次比较？那么，平均值为 (2+9)/2，即 5 次或 6 次比较？

还是我现在太天真了？

尝试#2

(a) 好的，所以，按照唐的建议，我非常努力地将比较次数减少到 3。从数学上讲，我理解你的意思。从中检查并扣除其余状态就足够了a<b, b<c, a<c，但是我找不到对其进行编码的方法...这是我最好的尝试：

medianOf(int a, int b, int c)
    if a < b                                  1
        if c < a                              1
            return a    //c < a < b
        else  // a < b && a < c
            if b < c                          1
                return b    //a < b < c
            else
                return c    //a < c < b    

    else    //a > b
        if c > a                              1
            return a    //c > a > b
        else //a > b && a > c
            if b > c                          1
                return b    //a > b > c
            else                
                return c    //a > c > b

我看不出我能做得比这更好：

(b) 最佳情况：1 次比较。平均情况：5/2 = 2 到 3 次比较。最坏情况：5 次比较。

好点？

最终解决方案

感谢thang，经过一番努力，终于搞定了。我的最后一个算法是正确的，但我的计数是错误的。

(b) 最佳情况：2 次比较。平均情况：2 次比较。最坏情况：3 次比较。

4

2 回答 2

4

幸运的是，我认为你想多了。:-) 这样想——你能实现这个功能吗？

 int medianOf(int a, int b, int c) {
      ...
 }

您不必担心找到任意集合的中位数。只需找到三个输入的中位数。

完成此操作后，请查看您所做的比较，并考虑最佳情况、最坏情况和平均情况的比较次数。您可以直接计算进行了多少比较，因为您的代码应该很短。

您正在考虑的中位数技术适用于更一般的情况，即您有任意数量的元素并希望获取所有元素的中位数。它肯定比这更复杂，但这似乎不是你被要求做的事情。

希望这可以帮助！

于 2015-02-18T20:56:33.433 回答
0

暗示：

如果 a <= b 且 b <= c，则 b 是中位数。

如果 a <= b 且 b > c 且 c >=a，则 c 是中位数。

如果 a<=b 且 b > c 且 c < a，则 a 为中位数。

如果 a >= b 且 b >= c，则 b 是中位数。

如果 a >= b 且 b < c 且 a >= c，则 c 是中位数。

如果 a >=b 且 b < c 且 a < c，则 a 是中位数。

您可以在嵌套的 if/else 语句中对此进行编码，以便在返回答案之前执行 2 或 3 次比较。唯一的问题是比较次数的最坏情况、最好情况和平均情况。对于平均情况，您可能不得不假设所有 3 个数字都是不同的（但以随机顺序），否则“等于”情况可能会根据发生的频率改变平均比较次数。

于 2015-02-19T00:59:23.510 回答