arrays - 查找修改数组以满足条件的最小操作集

Question

我有一个排序数字数组:

arr = [-0.1, 0.0, 0.5, 0.8, 1.2]

我希望该数组的连续数字之间的差异(dist 下面)高于给定阈值。例如，如果阈值为 0.25:

dist = [0.1, 0.5, 0.3, 0.4] # must be >0.25 for all elements

arr[0] 和arr[1] 距离太近，必须修改其中一个。在这种情况下，所需的数组将是:

good_array = [-0.25, 0.0, 0.5, 0.8, 1.2] # all elements distance > threshold

为了得到good_array，想修改arr中元素的最小数量。所以我从 arr[0] 中减去 0.15，而不是从 arr[0] 中减去 0.1，然后将 0.05 添加到 arr[1] :

[-0.2, 0.05, 0.5, 0.8, 1.2]

之前的数组也是有效的，但我们修改了 2 个元素而不是一个。

此外，如果可以通过修改 arr 中的不同元素来生成 good_array，默认情况下修改靠近数组边缘的元素。但请记住，主要目标是通过修改 arr 中元素的最小数量来生成 good_array。

[-0.1, 0.15, 0.5, 0.8, 1.2]

之前的数组也是有效的，但是我们修改了arr[1]而不是靠近边缘的元素(arr[0])。如果 2 个元素与边缘的距离相等，请修改靠近数组开头的元素:

[-0.3, 0.15, 0.2, 0.7] # modify arr[1] rather than arr[2]

到目前为止，我一直在为小型阵列手动执行此操作，但我想要一个适用于大型阵列的通用解决方案。

Answer 1

这是蛮力 python 解决方案，当存在冲突时，我们尝试将元素固定在右侧或左侧:

def solve(arr, thereshold):
    original = list(arr)

    def solve(idx):
        if idx + 1 >= len(arr):
            return [sum(1 for x in range(len(arr)) if arr[x] != original[x]), list(arr)];

        if arr[idx + 1] - arr[idx] < thereshold:
            copy = list(arr)    

            leftCost = 0
            while idx - leftCost >= 0 and arr[idx + 1] - arr[idx - leftCost] < thereshold * (leftCost + 1):
                arr[idx - leftCost] = arr[idx - leftCost + 1] - thereshold
                leftCost += 1

            left = solve(idx + 1)
            for cost in range(leftCost):
                arr[idx - cost] = copy[idx - cost]  

            rightCost = 0
            while idx + rightCost + 1 < len(arr) and arr[idx + rightCost + 1] - arr[idx] < thereshold * (rightCost + 1):
                arr[idx + rightCost + 1] = arr[idx + rightCost ] + thereshold
                rightCost += 1

            right = solve(idx + 1)
            for cost in range(rightCost):
                arr[idx + cost + 1] = copy[idx + cost + 1]  

            if right[0] < left[0]:
                return right
            elif left[0] < right[0]:
                return left
            else:
                return left if idx - left[0] <= len(arr) - idx - right[0] else right 

        else:
            return solve(idx + 1)               


    return solve(0)

print(solve([0,0.26,0.63,0.7,1.2], 0.25))