题目浅析

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

  • 简单地说，就是给一个数组，你要进行操作使得数组中元素各不相同或变成空数组，该操作为去除数组前三个元素。

思路分享

1. 顺着题目走

  • 直接用代码来模拟这个过程，听着容易，做着不算难，不过通过一些小细节能够优化这个过程。

  • 比如，陆爻齐第一次就用 unordered_map 作为哈希存储重复值，但是后来发现，数值大小为 1-100，于是就可以用长度 100 的整形 vector 来存储，速度和消耗内存也有所提升。

  • 嘛，说回题目的模拟思路，首先遍历 nums 来初始化 hash，每个数字对应的数字表示其个数，并且用另一个整数来记录重复数字个数。

  • 模拟过程中，陆爻齐采用双指针，左指针从 nums[0] 开始向右每次模拟三步，若有遇到数字是重复的，则更新哈希值，哈希值减少到一定程度就更新记录重复数字的个数变量，直到右指针的末尾或者没有重复数字。

2. 逆推法

  • 从模拟的方法来看，其实倒着看更快，毕竟至少后面的部分不重复就行。所以思路就是倒着数不重复的数量，然后计算剩余包含重复数字的部分长度，将该长度整除三就是答案。
  • 该方法麻烦在要准确地计算数字的关系，说实话，挺麻烦的，思维上，还是模拟法比较节约脑子。

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

  1. 模拟解法
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
class Solution {
public:
    // unordered_map<int, int> rec;
    int minimumOperations(vector<int>& nums) {
        vector<int> rec(101, 0);
        int over_single_count = 0;
        for (int & n : nums) {
            rec[n]++;
            if (rec[n] == 2) {
                over_single_count++;
            }
        }

        int left = 0;
        int right = nums.size();
        int least_oper_count = 0;
        while(over_single_count > 0 && left < right) {
            least_oper_count += 1;
            for (int i = left; i < left + 3 && i < right; i++) {
                rec[nums[i]] -= 1;
                if (rec[nums[i]] == 1) {
                    over_single_count -= 1;
                }
            }
            left += 3;
        }

        return least_oper_count;
    }
};
  1. 逆推解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int minimumOperations(vector<int>& nums) {
        int size = nums.size();
        vector<bool> rec(101, false);
        int not_over_count = 0;
        for (auto it = nums.rbegin(); it < nums.rend(); it++) {
            if (!rec[*it]) rec[*it]=true;
            else break;
            not_over_count++;
        }
        return (size-not_over_count)%3==0 ? (size-not_over_count)/3 : (size-not_over_count)/3+1;
    }
};