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)(即表示所有输入数字所需的总位数)。预计算循环变量可能比在循环中包含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 = ...

但是我还没有实际测量。

关于python - k次运算后求最小和的更有效方法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/54885971/