java - 数组中的相等元素

Question

今天我面试了，被问了一个问题，我什至都听不懂。

问题:

Given one array 𝑎 consisting of 𝑛 integers.

Get at least 𝑘 equal elements in the array 𝑎.

While calculating, you can do below two operations

• Take one of the minimum elements of the array and increase its value by one (more formally, if the minimum value of 𝑎 is 𝑚𝑛 then you choose such index 𝑖 that 𝑎𝑖=𝑚𝑛 and set 𝑎𝑖:=𝑎𝑖+1);

• take one of the maximum elements of the array and decrease its value by one (more formally, if the maximum value of 𝑎 is 𝑚𝑥 then you choose such index 𝑖 that 𝑎𝑖=𝑚𝑥 and set 𝑎𝑖:=𝑎𝑖−1).

Calculate the minimum number of moves required to obtain at least 𝑘 equal elements in the array.

任何人都可以帮助我理解，真正的问题是什么，以便我可以编写代码吗？

Answer 1

直接回答你的问题，即“帮助我理解问题”:

例如，这是您的数组:

{1,2,5,7,8,3}

现在，您只能执行这两个操作:

1. 找到最小元素并增加它:

{2,2,5,7,8,3} // <-- increased 1

1. 减少最大元素:

{2,2,5,7,7,3} // <-- decreased 8

现在的问题是:使这个数组包含 k 个相同数字的最少移动次数是多少？

---

因此，如果 k = 3 并且数组与上面类似，那么解决方案之一就是运行操作 1 三次:

1. 在任何移动之前:

{1,2,5,7,8,3}

1. 第一步之后:

{2,2,5,7,8,3} // <-- `1` changed to `2`

1. 第二步后:

{3,2,5,7,8,3} // <-- `2` changed to `3`

1. 第三步之后:

{3,3,5,7,8,3} // <-- `2` changed to `3`

因此生成的数组将是:

{3,3,5,7,8,3}

---

你现在明白问题了吗？