algorithm - 无序集合的中位数

Question

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

The median of an unordered set is an element such that the number of elements less than the median is within one of the number of elements that are greater, assuming no ties.

(a) Write an algorithm thst find the median of 3 distincts values a, b, c.

(b) Determine the number of comparisons your algorithm does in the average case and in the worst case.

从我搜索和了解的一点点来看，这似乎叫做找到未排序数组的第 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) 好的，所以，按照 thang 的建议，我非常努力地将比较次数减少到 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 次比较。

Answer 1

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

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

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

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

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

希望这对您有所帮助!