3012. 通过操作使数组长度最小（Rating 1832）

以下内容偏向于记录个人练习过程及思考，非常规题解内容

题目

3012. 通过操作使数组长度最小

Rating 1832

思路

开始时，考虑一组数之间互相取模应该有什么性质，猜测最终的数值应该可以推出来，于是就卡住了…

看了若干题解，才大概理清思路。

首先，为了使数组长度最小，我们应该尽量去消除数组中的数。题目中没有规定取模计算时的大小顺序，那么如果我们利用

较小的数 % 较大的数

就一定能获得原来较小的数，那么按照题目规则，较大的数即可被干掉。

由此，一组数中最小的数，可以把这组数中所有比它大的数干掉，最终答案即为1

但是，最小的数字有多个该如何处理？

关键思路：按照题目规则构造出来一个比它更小的数，就可以把其它数全干掉，最终答案为1

例如，我们有[2, 2, 2, 3]，最小的2有3个。如果我们先让3%2=1，那么就可以马上构造出来一个数字1比其它所有数字都小，然后按照上面的逻辑，就又可以答案为1了。

那假如数组中没有类似的构造怎么办？那只能剩下的这些最小数两两计算取余得到一堆0了。

例如，我们有[2, 2, 2, 4]，把4消掉可以得到[2, 2, 2]，两两对消最终得到输出[0, 2]，答案为2

理清思路，开始写代码

代码

class Solution:
    def minimumArrayLength(self, nums: List[int]) -> int:
        m = min(nums) # 计算数组中最小的数
        cnt = 0 # 统计最小的数有多少
        for num in nums:
            if num % m > 0: # 如果有对最小值m取余仍大于0的数存在，那说明我们可以构造出比m还小的数，把其它数都干掉，答案为1
                return 1
            if num == m: # 统计最小的数有多少
                cnt += 1
        return (cnt + 1) // 2 # 如果对最小值m取余仍大于0的数不存在，那么只能两两对消。注意对消时多出的数也会留下，应该向上取整