无序集合的中位数
The median of an unordered set
我是一名 compsci 学生，我在 Analysis & Design II 中遇到了以下问题 class：
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 次比较。
幸运的是，我认为你想多了。 :-) 这样想 - 你能实现这个功能吗？
int medianOf(int a, int b, int c) {
...
}
您不必担心找到任意集合的中位数。只需找到三个输入的中位数即可。
完成后，查看您所做的比较，并考虑最佳情况、最坏情况和平均情况下的比较次数。您可以直接计算您进行了多少次比较，因为您的代码应该很短。
您所考虑的中位数技术适用于更一般的情况，即您有任意数量的元素并希望取所有元素的中位数。它肯定比这更复杂，但这似乎不是你被要求做的。
希望对您有所帮助！
提示：
如果 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 语句中对此进行编码，以便在 return 答案之前执行 2 或 3 次比较。唯一的问题是比较次数的最坏情况、最好情况和平均情况。对于一般情况，您可能不得不假设所有 3 个数字都是不同的（但顺序是随机的），否则 "equals" 情况可能会根据发生的频率改变平均比较次数。
我是一名 compsci 学生，我在 Analysis & Design II 中遇到了以下问题 class：
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 次比较。
幸运的是，我认为你想多了。 :-) 这样想 - 你能实现这个功能吗？
int medianOf(int a, int b, int c) {
...
}
您不必担心找到任意集合的中位数。只需找到三个输入的中位数即可。
完成后，查看您所做的比较，并考虑最佳情况、最坏情况和平均情况下的比较次数。您可以直接计算您进行了多少次比较，因为您的代码应该很短。
您所考虑的中位数技术适用于更一般的情况，即您有任意数量的元素并希望取所有元素的中位数。它肯定比这更复杂，但这似乎不是你被要求做的。
希望对您有所帮助！
提示：
如果 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 语句中对此进行编码，以便在 return 答案之前执行 2 或 3 次比较。唯一的问题是比较次数的最坏情况、最好情况和平均情况。对于一般情况，您可能不得不假设所有 3 个数字都是不同的（但顺序是随机的），否则 "equals" 情况可能会根据发生的频率改变平均比较次数。