时间戳

首页 > 解决方案 > 找到修改数组以满足条件的最小操作集

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

问题描述

我有一个排序数字数组：

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

我希望该数组的连续数字之间的差异（下面的差异）高于给定阈值。例如，如果阈值为 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中的最小元素数量。所以我减去 0.15arr[0]而不是，比如说，减去 0.1arr[0]并将 0.05 添加到arr[1]：

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

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

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

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

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

标签： arraysalgorithm

解决方案

这是暴力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))

推荐阅读