添加到数组的最小元素数，使其中值等于 x

Question

我试图理解一个算法，给定一个数组 A 和一个整数 x，returns为了使 x 成为中位数，需要添加到 A 的最小元素数。

算法如下所示：

考虑中位数始终是位置 (n-1)/2 处的元素

n := |A|

m := 0
for i := 1 to n:
    if (A[i] < x) then:
        m++

if (m < n - m) then:
    return (n - 2 * m)
else:
    return (2 * m – n + 1)

我理解如果m等于n-m，那么数组大小是偶数，所以我们可以在(n-1)/2位置添加想要的中位数，这将是我们新的中位数。

我正在为 m 低于 n-m 的情况而苦恼，我们 return (n-2m)

或者m大于n-m，然后return(2*m-n+1)

**为什么是这样？

我找不到证据，如果你能提供的话，或者用简单的语言解释一下会很有帮助！**

Answer 1

我怀疑您误解了中位数是位置 (n - 1) / 2 处元素的含义。并不是说中值元素就是数组中那个确切位置的元素。相反，如果您要对数组进行排序，它就是位于该位置的元素。

例如，考虑数组

[31, 41, 59, 26, 53, 58, 97]

假设我们想让数字 93 成为中位数。让我们考虑一下我们必须做些什么才能实现这一目标。对于初学者来说，为了使 93 成为中位数，我们需要将其添加到数组中，如下所示：

[31, 41, 59, 26, 53, 58, 97, 93]
                             ^^

现在，如果我们对数组进行排序，93 会在什么位置？让我们实际对数组进行排序以找出：

[26, 31, 41, 53, 58, 59, 93, 97]
                         ^^

注意它在数组中的位置 6。那不是数组的中间，为了让这个元素在中间位置结束，我们需要在 93 之后插入更多的值，足以填充数组，使 93 位于中间。例如，我们可以添加一些额外的 99，如下所示：

[26, 31, 41, 53, 58, 59, 93, 97, 99, 99, 99, 99, 99]
                         ^^      ^^  ^^  ^^  ^^  ^^

所以在这种情况下，我们必须向数组添加总共五个元素才能得到 93 作为中位数。

现在，有一个问题需要考虑：为什么我们得到五个答案？其原因如下。根据您的算法中的符号，我们需要确保小于 93 的元素数（我们将用 m 表示）等于大于 93 的元素数。元素数数组中当前存在的大于 93 的元素由 n - m 给出，因为这是数组的所有元素，减去小于 93 的元素。

所以假设我们将 93 本身添加到数组中，同时将大于 93 的 k 个元素添加到数组中，以尝试将 93 放在中间位置。综上所述，我们需要让小于93的元素个数（m）必须比整个数组中大于等于93的元素个数（[=20）少1 =]，已经大于或等于93的元素，加上k，我们添加的额外元素的个数）。这里的 -1 项说明了这样一个事实，即当我们进行除法以计算中位数位置时，我们向下舍入。这意味着我们有

m - 1 = n - m + k

或者，那个

k = 2m - n + 1

嘿，看！就是2*m - n + 1，也就是我们在m≥n - m的情况下return，意思是这个数大于等于数组元素的一半以上。

另一方面，让我们return到我们的原始数组，如下所示：

[31, 41, 59, 26, 53, 58, 97]

假设我们要使 27 成为中值元素。我们首先添加 27，如下所示：

[31, 41, 59, 26, 53, 58, 97, 23]
                             ^^

现在，如果我们对元素进行排序，我们会得到以下结果：

[26, 27, 31, 41, 53, 58, 59, 97]
     ^^

这不在中间位置，因此我们将不得不添加更多元素来填充数组。让我们想象一下添加一堆较小的元素来填充内容，如下所示：

[13, 13, 13, 13, 26, 27, 31, 41, 53, 58, 59, 97]
 ^^  ^^  ^^  ^^      ^^

看来这次又需要五个元素了。这是为什么？和以前一样，假设我们要将 k 个元素添加到数组中。我们需要这样

小于27的元素个数(m)，加上(k)中加入的元素个数，比
大于等于27的元素个数(n - m)减一因为newly-added27会算作大于等于的元素之一本身。

也就是说，我们需要

m + k = n - m,

或者那个

k = n - 2m.

这给了我们构成第二种情况的 n - 2 * m。

所以总而言之 - 这里的数学运算是因为我们试图填充数组以使包含要添加的数字的边与较小的边具有相同的长度，而如何做到这一点的数学运算取决于关于我们是在数组的前半部分还是后半部分。

希望对您有所帮助！

添加到数组的最小元素数，使其中值等于 x

Minimum number of elements to add to an array, to make its median equal to x

algorithm

median