删除满足条件的元素时如何找到数组的最小可能大小

Question

在一次操作中给定一个包含 n 个整数的数组 arr，可以选择两个索引 i 和 j，并从数组中删除 arr[i] 如果 2*arr[i] <= arr[j]

执行任意次数（可能为零）的操作后，一旦找到数组的最小可能大小，最多可以选择一个特定元素。

示例：

假设 n=7 且 arr = [1, 2, 3, 4, 16, 32, 64]

第一个操作中，选择1和16，将1作为2*1从数组中删除<= 16. The array becomes [2, 3, 4, 16, 32, 64]

第二个操作中，选择2和32，将2作为2*2从数组中删除<= 32. The array becomes [3, 4, 16, 32, 64]

第三次操作，选择4和64，将4作为2*4从数组中删除<= 64. The array becomes [3, 16, 32, 64]

现在唯一没有选择的元素是 3。必须有两个元素 arr[i] 和 arr[j] 才能进行比较，因此不能再进行任何操作。数组的最小可能大小为 4。请注意，执行操作后，有多种方法可以在最终数组中实现 4 个元素。

函数说明：在下面的编辑器中完成函数getMinSize。 getMinSize 有以下参数：

arr[n]：整数数组。

返回：

int：数组的最小可能大小。

def getMinSize(arr):
    arr.sort()
    n = len(arr)
    deleted = [False] * n
    count = 0
    
    for i in range(n):
        if not deleted[i]:
            for j in range(i+1, n):
                if not deleted[j] and arr[i] * 2 <= arr[j]:
                    deleted[i] = True
                    deleted[j] = True
                    count += 1
                    break

    return n - count

这个解决方案可以通过示例，但当测试用例为{1,2,4,6}时会失败。它输出 3，但预期答案是 2。

Answer 1

您当前的代码不起作用，因为算法逻辑无法解决问题。它将“1”和“2”标记为删除，然后检查“4”和“6”。但它应该标记“1”和“4”并删除，然后检查“2”和“6”。

因为“一个特定元素最多只能被选择一次”，所以你可以将已排序的数组分成两半，然后一一比较这两半的元素。

以下是根据您的代码修改的代码：

def getMinSize(arr):
    arr.sort()
    n = len(arr)
    deleted = [False] * n
    count = 0
    j=int(n/2)
    for i in range(int(n/2)):
        while j < n:
            if arr[i] * 2 <= arr[j]:
                #delete i,and use j
                count += 1
                j+=1
                break
            j += 1

    return n - count

print(f"Testing getMinSize(): {getMinSize([1, 2, 4, 6])}")