Leetcode 3012. Minimize Length of Array Using Operations

本文主要是介绍Leetcode 3012. Minimize Length of Array Using Operations，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

• Leetcode 3012. Minimize Length of Array Using Operations
  • 1. 解题思路
  • 2. 代码实现

• 题目链接：3012. Minimize Length of Array Using Operations

1. 解题思路

这一题有一点数学题的意思，显然，根据最大公约数相关的知识，我们知道，对任意两个数反复相减，我们即可得到他们的最大公约数。

因此，这里，我们显然可以通过有限次操作，获得数组当中所有数的最大公约数。

然后，如果有一个数比其他数小，不妨设为$x$，那么其他所有的数$y_i$都可以通过$x\equiv y_i(modx)$进行消除，于是总可以去除掉所有比$x$大的数。

结合上述两个结论，我们不难看到：

• 我们可以通过有限次操作获得的最小的数一定是所有数的最小公约数，且原数组中任意比这个最小公约数大的数都可以被消掉。

因此，我们最后留下的一定就是若干个最小公约数，而对于他们，我们能够消除后保留的数目最少也会有$\lceil \frac{n}{2}\rceil$。

2. 代码实现

给出python代码实现如下：

class Solution:def minimumArrayLength(self, nums: List[int]) -> int:elems = sorted(set(nums))_gcd = elems[0]for x in elems[1:]:_gcd = gcd(_gcd, x)if _gcd == 1:breakif _gcd in elems:return (Counter(nums)[_gcd] + 1) // 2else:return 1

提交代码评测得到：耗时604ms，占用内存36.3MB。

这篇关于Leetcode 3012. Minimize Length of Array Using Operations的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---