从阵列中删除最大的项目，并将其中的一半添加回相同的位置

Question

如何从数组中删除最大的整数，并将该数字的一半（向上舍入）添加回相同位置的数组中。做到这一点。

我解决了这个问题，但速度很慢。 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)

以上示例仅适用，因为它是一个小数组。

编辑：到目前为止，我所做的唯一改进如下所述。管理通过单元测试中的5个中的5个。

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

Answer 2

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

可能会快一点

Answer 3

我认为这会更快（仅使用内置插件）：

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(n):
    max_index = max(enumerate(num), key=lambda pair: pair[1])[0]
    num[max_index] = math.ceil(num[max_index]/2)

Answer 4

C ++解决方案

---

将所有元素插入C ++最高优先级队列。接下来的n个步骤：

• 弹出第一个元素（需要O（1）时间）
• 将它的一半插入优先级队列（占用log（n）时间）。