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

问题描述

小U有一个数组，她可以通过选择一个元素并将其除以2（向下取整）的操作来改变数组。小U想知道，最少需要多少次这样的操作才能使得所有数组元素相等。

解题思路

本题要求通过对数组中的元素进行除以 $2$ 的操作，使得所有元素相等，并求出最小的操作总次数。

具体思路如下：

  1. 记录每个元素能够通过多少次操作达到哪些值：
    • 对于数组中的每个元素，模拟其不断除以 $2$ 的过程，记录它能够到达的所有值以及到达每个值所需的操作次数。
    • 使用哈希表（如 unordered_map 来存储每个可能的目标值对应的操作次数列表。
  2. 汇总所有元素可达到的公共值：
    • 遍历哈希表，对于每个可能的目标值，检查是否所有元素都能够通过某些操作达到该值（即操作次数列表的长度是否等于数组长度 n ）。
    • 如果是，则计算将所有元素变为该值所需的操作总次数。
  3. 求最小的操作总次数：
    • 在所有可能的目标值中，选择操作总次数最小的值，即为所求答案。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>
using namespace std;

int solution(int n, vector<int> a)
{
    unordered_map<int, vector<int>> cnt;
    for (int num : a)
    {
        int op = 0;
        int x = num;
        while (x)
        {
            cnt[x].push_back(op); // 该元素除到x所需要的操作数
            x /= 2;
            op++;
        }
    }

    int res = INT_MAX;
    for (auto &k : cnt)
        if (k.second.size() == n) // 该数是所有元素都能除到的
        {
            int total = 0;
            for (int i = 0; i < n; i++)
                total += k.second[i]; // 累加每个元素除到该数所需要的操作
                
            res = min(res, total); // 取最小值
        }
    return res;
}

int main()
{
    cout << (solution(4, {1, 2, 1, 3}) == 2) << endl;
    cout << (solution(1, {114514}) == 0) << endl;
    cout << (solution(5, {16, 8, 4, 2, 1}) == 10) << endl;
}

代码解析

操作记录

  • 遍历数组：对于每个元素 num ，不断将其除以 $2$，记录每个中间值 x 以及到达该值所需的操作次数 op 。
  • 哈希表存储：使用 cnt[x] 来存储能够通过操作达到值 x 的所有操作次数。

汇总最小操作次数

  • 遍历哈希表：
    • 对于每个可能的目标值 k.first ，检查其对应的操作次数列表 k.second 长度是否等于数组长度 n ，保证所有元素都能通过操作达到该值。
  • 计算总操作次数：
    • 计算前 n 个操作次数的和，即为将所有元素变为该值的最小总操作次数。
    • 比较并更新最小的操作总次数 res 。

知识点总结

  • 贪心算法：每次选择最优（操作次数最少）的方案，保证全局最优。
  • 哈希表：用于记录并快速查询每个可能的目标值及其对应的操作次数列表。

时间复杂度

  • 记录操作数：遍历数组中的 $n$ 个元素， $A$ 为数组中最大元素，对其进行 $O(\log A)$ 次操作，总共 $O(n \log A)$ 。
  • 寻找最小总操作数：遍历哈希表，假设哈希表的大小为 $M$，总复杂度为 $O(M \log n)$。
  • 总体时间复杂度：$O(n \log A + M \log n)$。

空间复杂度

  • 哈希表存储：需要 $O(n \log A)$ 的空间来存储所有可能的操作次数。

总结

本题通过对每个元素模拟除以 $2$ 的过程，记录可能的目标值和所需的操作次数，利用贪心思想，选择使所有元素相等的最小操作总次数。关键在于：

  • 记录每个元素的可能状态及对应的操作次数。
  • 汇总并计算公共目标值的最小操作次数。