题解-通过操作使数组长度最小筑-脑筋急转弯,用小数踢掉大数

Problem: 100164. 通过操作使数组长度最小

思路

1. 观察$nums[i]%nums[j]$有如下的可能性
   • 如果$nums[i]<nums[j]$,最后只是将数组中的$nums[j]$踢出
   • $nums[i]>=nums[j]$则是二者踢出,$nums[i]%nums[j]$进入数组,且显然$nums[i]%nums[j]<nums[j]<=nums[i]$
2. 因为没有限定ij的关系,发现这种操作要么是小数将大数从数组中踢掉,要么是引入一个更小的数,将二者踢掉
3. 最后剩下的长度应该和数组中最小值有关,且这个最小值包括操作中可能产生的
4. 如果没有产生新的最小值,则很容易知道最后剩下的数就是原始数组中最小值的数量,然后将其两两组合,引进0,就能得到答案
5. 如何产生更小值:
   • 回顾1,我们将所有数与最小值相模
   • 如果余数不为0,就为新的最小值
   • 如果余数全为0,说明所有数都是最小值的倍数,则它们之间两两相模的最小值大于等于原始数组的最小值
6. 我们只需要产生一个新的更小值就能把所有其他数都踢掉,此时答案是1

时间复杂度:$O(n)$

Code

class Solution:
    def minimumArrayLength(self, nums: List[int]) -> int:
        m=min(nums)
        for num in nums:
            if num%m!=0:# 可以产生新的最小值
                return 1
        length=nums.count(m)
        return length//2+length%2