algorithm - 要添加到数组中使其中位数等于x的最小元素数

Question

我试图理解一个算法，给定一个数组A和一个整数x，返回需要添加到A的元素的最小数量，以便x是中值。
算法如下：
假设中值始终是位置（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时，我正在努力解决这个问题，然后我们返回（n-2m）
或者m大于n-m，然后返回（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]
                         ^^      ^^  ^^  ^^  ^^  ^^

所以在这种情况下，我们需要向数组中添加总共5个元素，得到93作为中值。
现在，有一个问题需要考虑：为什么我们得到的答案是5？原因如下。根据算法中的符号，我们需要确保小于93的元素数（我们将用 m表示）等于大于93的元素数。数组中当前存在的大于93的元素的数量由 n - m给出，因为这是数组的所有元素，减去小于93的元素。
因此，假设我们将93本身添加到数组中，并将大于93的元素添加到数组中，以尝试将93放置在中间位置。根据我们上面所说的，我们需要得到小于93的元素数（ k）必须小于整个数组中大于或等于93的元素数（ m，已经大于或等于93的元素，加上我们添加的额外元素数）。这里的-1项解释了这样一个事实：当我们做除法来计算中间位置时，我们会四舍五入。也就是说我们会
m-1=n-m+k
或者，那
K=2米-N+1
嘿，看！它是 n - m，这是我们在 k> 2*m - n + 1的情况下返回的值，这意味着数字大于或等于数组元素的一半以上。
另一方面，让我们回到原来的数组，如下所示：

[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]
 ^^  ^^  ^^  ^^      ^^

看来这次我们又需要五个元素为什么？如前所述，假设我们将 mtotal元素添加到数组中我们需要这个
小于27（ n - m）的元素数加上（ k）中添加的元素数是小于1的
大于或等于27的元素数（ m），减去1，因为新添加的27将被视为大于或等于自身的元素之一。
换句话说，我们需要
m+k=n-m，
或者那个
K=N-2m。
这给了我们组成第二个案例的 k。
所以总结一下，这里的数学是因为我们试图填充数组，使包含要添加的数字的边与较小的边具有相同的长度，而如何这样做的数学取决于我们是在数组的上半部分还是下半部分。
希望这有帮助！