python之在 k 操作后找到最小和的更有效方法

一个数组被操作 k 次，以便每次最大值除以 2 并向上舍入。 在这 k 次操作之后，我需要找到它的最小总和。 k 和数组 num > 1 中的所有数字。 minSum 方法接收一个名为 num 的数组和一个整数 k。 对我来说时间复杂度非常低的粗暴 Python 代码是:

import bisect 
 
def minSum(num, k): 
    num.sort() 
    lastIndex = len(num)-1 
    for i in range(k): 
        if num[lastIndex]==1: 
            return sum(num) 
 
        num[lastIndex]= math.ceil(num[lastIndex]/2) 
        lastNumber = num[len(num)-1] 
        num.pop() 
        bisect.insort(num, lastNumber) 
 
    return sum(num) 

我也曾尝试先对数组进行排序，但随后我尝试的每个算法都失败了。 你能想出一个时间复杂度好的算法吗？最好不使用特殊进口。

请您参考如下方法:

标准库(即没有特殊导入)带有一个 heapq 模块，使算法 O(3n + k*(2 lg n)) => O(lg n):

import math 
import heapq 
 
def minSum(num, k): 
    heap = [-n for n in num]  # negate values for max-heap 
    heapq.heapify(heap) 
 
    for i in range(k): 
        # Find max value 
        max_value = heapq.heappop(heap) 
        # Change max value to rounded half 
        # use floor since we've negated the values 
        heapq.heappush(heap, math.floor(max_value/2)) 
 
    # Calculate minimum sum 
    return -sum(heap)  # reverse polarity again 

更新 1:(来自@raury-daulton 的评论)组合 pop/push，O(3n + k*(lg n)) => O(lg n):

def minSum(num, k): 
    heap = [-n for n in num]  # negate values for max-heap 
    heapq.heapify(heap) 
 
    for i in range(k): 
        max_value = heap[0] 
        heapq.heapreplace(heap, math.floor(max_value/2)) 
 
    # Calculate minimum sum 
    return -sum(heap)  # reverse polarity again 

更新 2:直接使用最大堆 O(2n + k*(lg n)) => O(lg n)

def heapreplace_max(heap, item): 
    "We need to implement this ourselves from primitives." 
    returnitem = heap[0] 
    heap[0] = item 
    heapq._siftup_max(heap, 0) 
    return returnitem 
 
 
def minSum(num, k): 
    heap = num   # alias for consistency with other samples 
    heapq._heapify_max(heap)  # make it a max heap (no negation hack) 
 
    for i in range(k): 
        max_value = heap[0] 
        heapreplace_max(heap, math.ceil(max_value/2)) 
 
    return sum(heap) 

更新 3: 最终优化(这要求输入数组是 int 数组)。

def minSum(num, k): 
    heap = num   # alias for consistency with other samples 
    heapq._heapify_max(heap) 
 
    for i in range(k): 
        max_value = heap[0] 
        if max_value == 1:  # exit early if there is no more work 
            break 
        new_val = (max_value >> 1) + (max_value & 1)  # same as, but much faster than math.ceil(max_value/2) 
        heapreplace_max(heap, new_val) 
 
    return sum(heap) 

k 的上限是 sum(math.floor(math.log(v, 2)+1) for v in num)(即表示所有 k 所需的总位数输入数字)。预先计算循环变量可能比在循环中使用 if max_value == 1: 更快，即:

for i in range(min(k, int(sum(floor(log(v, 2)+1) for v in num)))): 
    max_value = heap[0] 
    new_val = ... 

但我还没有实际测量过这个。