arrays - 长度为 K 的 N 个整数的神奇数组 A

Question

给定一个包含 N 个整数的数组 A，如果它的所有元素恰好有 3 个除数，则这个数组称为神奇数组。现在您必须将给定的数组转换为神奇的K 长度数组。您可以按任意时间顺序执行以下操作。

1. 将数组中任意元素的值加1。

2. 将数组中任意元素的值减1。

3. 删除数组的任意元素。

约束:

1 <= N <= 1000000
1 <= K <= N
1 <= A <= 1000000

Sample Input
5(size of the array) 3(K)
1 4 10 8 15

Output
4

我尝试过的解决方案:

迭代数组的每个元素，检查素数平方附近并将此差异添加到全局计数操作(用于计算所需操作的变量)。这个时间顺序是n^2。

寻找更好的解决方案。

Answer 1

用最接近的素数平方差的绝对值制作一个数组

使用QuickSelect分离 K 较小差异的算法(平均复杂度趋向于 O(N)，而最坏的二次情况是可能的)

计算它们的总和