时间戳

首页 > 解决方案 > 如果有序，使数组的每个元素连续的最小操作数

algorithm - 如果有序，使数组的每个元素连续的最小操作数

问题描述

给定一个数组，返回使数组的所有元素连续所需的最小操作数。在一次操作中，数组的任何元素都可以替换为任何整数。例如 =>

arr = [6, 4, 1, 7, 10]

输出应该是 ContinuousElementsArray(arr) = 2。通过转换 1 -> 5 和 10 -> 8 最终数组是

arr = [6, 4, 5, 7, 8]

连续意味着数字应该是连续的，如 {1,2,3} 或 {2,3,1}。这里顺序无关紧要。并且每个数字都应该是唯一的（不允许重复）。

标签： algorithmdata-structures

解决方案

怎么样：

让L你的数组的长度。然后，您首先要找到可以最小化您的转换的数字范围[Min,Max]。所以：

  1. 计算数组的直方图IniArray。
  2. 计算一个与直方图长度相同的数组，该数组具有1填充直方图箱的值，0否则（我将其称为Mask）。这一步几乎可以直接计算，无需在步骤（1）中计算直方图；它的计算方式与直方图相同，但不是将 +1 添加到 bin，而是将值分配给它们 '1'。
  3. 使用大小为 的滤波器计算此数组的均值滤波器L。这可以通过首先计算 的累积数组 ( Cummul)Mask然后取差来完成
 MeanFilter[i] = (Cummul[min(i+L/2,L-1)] - Cummul[max(0,i+L/2-L-1)])/L
  1. 最大值的索引 (I)MeanFilter将为您提供所需的范围。 [Min,Max]= [min(I+L/2,L-1) , max(0,I+L/2-L-1) ]. 如果最大值重复，则取其任何相应的索引。
  2. 令为范围内S的值的总和，则最小操作数计算为Mask[Min,Max]NN=L-S

如果顺序无关紧要，那么最终的数组就是从 Min 到 Max 的整数序列。如果您需要精确的转换操作，并且希望尽可能保持初始数组顺序：

  1. 创建一个长度为“L”的数组 ( Filled)，并将其所有值初始化为范围之外的值[Min,Max]。该值NFV将是参考值，意思是“尚未填充”。
  2. V对于初始数组中的每个元素，将其在直方图中的索引位置计算为J=V-Min。如果J<0或J>=L，暂时什么都不做。否则，如果Filled[J]==NFV，则设置Filled[J]=V; 否则什么也不做。
  3. 我们重复第 7 步，但这次我们将存储更改：对于IniArray[i]=V初始数组中的每个元素，将其在直方图中的索引位置计算为J=V-Min。如果J<0orJ>=L或Filled[J]!=NFV，遍历整个过程，Filled直到找到Filled[K]==NFV然后记下更改(IniArray[i]=V) => (K+Min)并更新 'Filled[K]==K+Min`

推荐阅读