python - 从数组中删除最大的项目并将其一半添加回相同的位置

Question

如何从数组中删除最大的整数并将该数字的一半(四舍五入)加回数组的相同位置。重复 n 次。

我解决了这个问题，但是速度很慢。由于解决时间太长，Hackerrank 不接受有效答案。

n = 10
num = [1,1,1,1,1,1,4,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8]

for i in range(0, n):
    index = num.index(max(num))
    num[index] = math.ceil(num[index]/2)

上面的例子之所以有效，是因为它是一个小数组。

编辑: 到目前为止，我所做的唯一改进如下所述。设法通过了十分之五的单元测试。

num.sort(reverse=True)
for i in range(0, n):
  num[0] = math.ceil(num[0] / 2)
  if len(num) > 1 and num[0] < num[1]:
    num.sort(reverse=True)

Answer 1

您可以尝试使用堆(假设您被允许使用额外的内存。)对于小输入，您的解决方案更快。但是对于大输入，堆似乎更快。我还为上面的一个答案计时。

import heapq
import math
import time
import random

n = 500
num = random.sample(range(10000), k=1000)
num_copy = list(num)
num_copy2 = list(num)

start = time.time()
tuples = list(zip([-n for n in num], range(len(num))))
heapq.heapify(tuples)
largest = heapq.heappop(tuples)
for i in range(n):
    new_item = (-math.ceil(-largest[0]/2), largest[1])
    largest = heapq.heappushpop(tuples, new_item)
heapq.heappush(tuples, largest)
for _ in range(len(num)):
    val, index = heapq.heappop(tuples)
    num[index] = -val
print(time.time() - start)

start = time.time()
num = num_copy
for i in range(0, n):
    index = num.index(max(num))
    num[index] = math.ceil(num[index] / 2)
print(time.time() - start)

start = time.time()
num = num_copy2
for i in range(n):
    max_index = max(enumerate(num), key=lambda pair: pair[1])[0]
    num[max_index] = math.ceil(num[max_index]/2)
print(time.time() - start)

输出:

0.0014951229095458984
0.007564067840576172
0.03954339027404785