题目浅析

  • 想查看原题可以点击题目链接。

  • 简单地说，就是只能用一种操作来使数组变化，即每次只能把最大值化为第二大值，最终可以将整个数组化为一个值K。其中，所有大于某个值I的数值都相同时，I 叫做合法值。求这个操作次数最小的值是多少。如果不能化为 K，则返回 -1.

思路分享

  • 普通的方法就是每次操作都暴力遍历所有值，但是复杂度应该是 O(n^2)。
  • 陆爻齐把求解的方法更抽象了些，实际上，要求整个数组是否能化为 K，必须要求 K 小于等于数组中的最小值。假设，K 大于数组的最小值，那么 K 就无法作为合法值来合并那些比 K 小的值。而求操作的最小值，实际上就是求有多少个值大于 K，因为每次合法值做合并都是把大于他的值合并成合法值，和大于合法值的数值只有一个数值。

代码解答（强烈建议自行解答后再看）

  • 陆爻齐的解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int minOperations(vector<int>& nums, int k) {
        vector<bool> is_rec(101, false);
        int min_num = INT_MAX;
        int over_k_count = 0;

        for (int &i : nums) {
            if (!is_rec[i]) {
                if (i < min_num) {
                    min_num = i;
                }
                if (i > k) {
                    over_k_count++;
                }
                is_rec[i] = true;
            }
        }

        if (k > min_num) return -1;
        else return over_k_count;
    }
};