英文:
Maxheap counting the total swaps needed when inputting an array [1 to N]
问题
我需要计算将数组[1到N]转化为最大堆所需的总交换次数。我的下面的代码输出了正确的答案，但我想知道是否有一种替代方法来完成相同的任务？
from math import floor, log2
def count(n):
layers = 0
for i in range(1, n+1):
layers += floor(log2(i))
return layers
if __name__ == "__main__":
print(count(4)) # 4
print(count(7)) # 10
print(count(123)) # 618
请注意，这是你提供的代码的翻译部分。
英文:
I need to count the total number of swaps needed to turn an array [1 to N] into maxheap. My code below outputs the correct answers but I was wondering if there was an alternative faster way to accomplish the same thing?
from math import floor, log2
def count(n):
layers = 0
for i in range(1, n+1):
layers += floor(log2(i))
return layers
if __name__ == "__main__":
print(count(4)) # 4
print(count(7)) # 10
print(count(123)) # 618
答案1
得分: 2
I found this Math StackExchange answer which, coupled with the base of 2 reducing the formula nicely, boils your function down to one formula:
from math import floor, log2
def count(n):
fl2n = floor(log2(n))
return fl2n*(n+1) + 2 - 2**(fl2n+1)
if __name__ == "__main__":
print(count(4)) # 4
print(count(7)) # 10
print(count(123)) # 618
To further optimize, we also know that floor(log2(n)) returns the biggest power of 2 smaller than n, which is exactly the bit length of n - 1. This is because the biggest power of 2 smaller than n is the one where 2**n has one bit in n's most significant digit. 2**n is also equal to 1 << n.bit_length(). Using these, we don't even need to import the math module!
def count(n):
return (n.bit_length()-1)*(n+1) + 2 - (1 << n.bit_length()) if n > 0 else 0
if __name__ == "__main__":
print(count(4)) # 4
print(count(7)) # 10
print(count(123)) # 618
英文:
I found this Math StackExchange answer which, coupled with the base of 2 reducing the formula nicely, boils your function down to one formula:
from math import floor, log2
def count(n):
fl2n = floor(log2(n))
return fl2n*(n+1) + 2 - 2**(fl2n+1)
if __name__ == "__main__":
print(count(4)) # 4
print(count(7)) # 10
print(count(123)) # 618
To further optimize, we also know that floor(log2(n)) returns the biggest power of 2 smaller than n, which is exactly the bitlength of n - 1. This is because the biggest power of 2 smaller than n is the one where 2**n has one bit in n's most significant digit. 2**n is also equal to 1 << n.bit_length(). Using these, we don't even need to import the math module!
def count(n):
return (n.bit_length()-1)*(n+1) + 2 - (1 << n.bit_length()) if n > 0 else 0
if __name__ == "__main__":
print(count(4)) # 4
print(count(7)) # 10
print(count(123)) # 618
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论