代码之家 › 专栏 › 技术社区 › Brenlla

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

algorithm arrays

Brenlla · 技术社区 · 7 年前

我有一个排序的数字数组:

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

我希望该数组的连续数字之间的差值(dist below)高于给定的阈值。例如,如果阈值为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

为了获得好的数组,我想修改arr中元素的最小数量,因此我将0.15减去 arr[0] 而不是,比方说,减去0.1 arr[0] 加0.05到 阿瑞[1] 以下内容:

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

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

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

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

前一个数组也是有效的,但是我们已经修改了 阿瑞[1] 而不是靠近边缘的元素( arr[0] )中。如果两个元素与边的距离相等,请修改一个更接近数组开头的元素:

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

到目前为止,我一直在手动为小数组做这个,但是我想要一个更大的数组的通用解决方案。

2 回复 | 直到 7 年前

juvian 7 年前

下面是brute force 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))

mpasko256 7 年前

编辑:我刚刚意识到我原来的解决方案是愚蠢和复杂的。现在提出简单更好的解决方案

第一种方法

如果我正确地理解了您的问题,那么您的输入数组可能有一些区域,而这些区域不符合您的条件。例如:

array = [0.0, 0.0, 0.0, 0.0, 0.0, 0.25, 0.5, 0.75, 1.0] (前4个元素)

或:

array = [0.25, 0.5, 0.75, 1.0, 1.0, 1.0, 1.0, 1.0, 1.25, 1.5, 1.75] (元素arr[4]、arr[5]和arr[6])

要解决这个问题,您必须添加(或减去)一些模式,如:

fixup = [0.0, 0.25, 0.0, 0.25, 0.0, 0.0, 0.0, 0.0, 0.0] (第一例)

或:

fixup = [0.0, 0.0, 0.0, 0.0, 0.25, 0.0, 0.25, 0.0, 0.0, 0.0, 0.0] (对于第二个示例)

第二种方法

但我们目前的解决方案有一些问题。考虑一个有“立面”的坏区域:

array = [0.0, 0.25, 0.5, 0.6, 0.7, 0.8, 0.9, 1.0, 1.1, 1.35, 1.6] (断面积在0.6-1.0范围内)

在这种情况下,我们正确的“解决方案”是:

fixup = [0.0, 0.0, 0.0, 0.25+0.1, 0.0, 0.25+0.1, 0.0, 0.25+0.1, 0.0, 0.0, 0.0]

产生:

good_array = [0.0, 0.25, 0.5, 0.95, 0.7, 1.15, 0.9, 1.0, 1.1, 1.35, 1.6]

总而言之,你必须应用“补丁”:

fixup[i] = threshold+max(difference[i], difference[i-1]) (用于 i 什么时候? i-start_index 是均匀的)

(请注意 -threshold+min(difference[i], difference[i-1]) 对于负值)

以及:

fixup[i] = 0 (用于 我 什么时候? i-start_索引 很奇怪)

start_index 是坏地区的开始。

第三途径

前面提到的公式在某些情况下不起作用(比如 [0.1, 0.3, 0.4] 它会增加 0.3 高达 0.75 只有当 0.65 已足够)

让我们试着改进一下:

good_array[i] = max(threshold+array[i-1], threshold+array[i+1]) (用于 abs(array[i-1]-array[i+1]) < threshold*2 )

以及:

good_array[i] = (array[i-1]+array[i+1])/2 否则。

(您也可以选择公式: good_array[i] = min(-threshold+array[i-1], -threshold+array[i+1]) 当它产生一个更接近原始数组值的结果时,如果最小化差异也是你的优化目标。

第四种方法

长度均匀的不良区域也是一个威胁。我可以想出两种解决方法:

基于如下模式的解决方案 [0.0, 0.25, 0.5, 0.0]
或者基于一个类似的模式 [0.0, 0.25, -0.25, 0.0] (我们只是使用“第二个公式”)
或者 [0.0, 0.25, 0.0, 0.25] (只是包括额外的元素,使坏的区域长度奇-我不推荐这种方法,因为它需要处理很多角落的情况)

角盒

也请考虑一些角点情况(坏区域开始或结束于数组的“边”):

good_array[0] = threshold+array[1]

以及:

good_array[array_size-1] = threshold+array[array_size-2]

最后提示

我建议在执行过程中实现大量单元测试,以便容易地验证导出公式的正确性,并处理角组合的一些组合。 只有一个元素的坏区域可以是其中之一。