433数组元素最小操作次数问题

题解

问题分析

我们需要将数组中的所有元素通过一系列“除以 2 并向下取整”的操作变得相等。目标是找到最少的操作次数使得所有元素相等。

解题思路

1. 记录每个数及其通过不断除以 2 后可能出现的值：

   • 对于数组中的每个元素 x，记录它本身及其通过不断除以 2 后得到的所有可能值。
   • 同时记录将 x 变成这些值所需的操作次数。

2. 使用哈希表统计：

   • 使用两个字典 cnt 和 d：
     • cnt[x]：记录值 x 出现的次数，即有多少个元素可以通过某些操作变成 x。
     • d[x]：记录所有将元素变成 x 所需的总操作次数。

3. 遍历所有可能的目标值，找到最小的总操作次数：

   • 遍历字典 cnt 中的所有键 x，如果 cnt[x] 等于数组的长度 n，表示所有元素都可以被转换为 x。
   • 在满足条件的 x 中，选择 d[x] 最小的作为答案。

代码实现

from collections import defaultdict

def solution(n: int, a: list) -> int:
    d = defaultdict(int)
    cnt = defaultdict(int)
    for x in a:
        cnt[x] += 1
        i = 0
        while x:
            i += 1
            x //= 2
            cnt[x] += 1
            d[x] += i
    res = min(d[x] for x in cnt if cnt[x] == n)
    return res

if __name__ == '__main__':
    print(solution(n = 4, a = [1, 2, 1, 3]) == 2)
    print(solution(n = 1, a = [114514]) == 0)
    print(solution(n = 5, a = [16, 8, 4, 2, 1]) == 10)

复杂度分析

• 时间复杂度： O(n log MAX)，其中 n 是数组的长度，MAX 是数组中最大元素的值。因为对于每个元素，最多需要进行 log(MAX) 次除以 2 的操作。
• 空间复杂度： O(n log MAX)，用于存储所有可能的中间值及其对应的操作次数。