【每日一题Day86】LC1819序列中不同最大公约数的数 | 数学

序列中不同最大公约数的数【LC1819】

You are given an array nums that consists of positive integers.

The GCD of a sequence of numbers is defined as the greatest integer that divides all the numbers in the sequence evenly.

• For example, the GCD of the sequence [4,6,16] is 2.

A subsequence of an array is a sequence that can be formed by removing some elements (possibly none) of the array.

• For example, [2,5,10] is a subsequence of [1,2,1,**2**,4,1,**5**,**10**].

Return the number of different GCDs among all non-empty subsequences of nums.

错过周赛了 送俺大侄子去医院了 找时间虚拟一下

• 思路

  • 由于数组中的最大公约数不可能超过子序列的最大值因此可以枚举所有可能的最大公约数来判断当前的公约数是否有子序列构成。
  • 那么如何判断是否有子序列能够得到当前枚举的gcd值呢
    • 首先最大公约数为x的子序列一定都是x的倍数但是都是x的倍数的最序列的最大公约数不一定是x但最大公约数一定是x的倍数比如子序列[6,12]都是3的倍数最大公约数为6。
    • 因此枚举所有x的倍数若存在于nums中则添加至当前子序列中更新最大公约数gcd若gcd==x那么退出循环个数加1。
      • 随着子序列个数的增加最大公约数只可能减小或者不变因此当gcd==x时退出循环即可

• 实现

  class Solution {
      public int countDifferentSubsequenceGCDs(int[] nums) {
          int max = 0, count = 0;
          for (int num : nums){
              max = Math.max(max, num);
          }
          boolean[] map = new boolean[max + 1];
          for (int num : nums){
              map[num] = true;
          }
          for (int i = 1; i <= max; i++){
              int gcd = 0;
              for (int j = i; j <= max; j += i){
                  if (map[j]) gcd = gcd(gcd, j);
              }
              if (gcd == i) count++;
          }
          return count;
      }
      public int gcd (int x, int y){
          while (y != 0){
              int tmp = x;
              x = y;
              y = tmp % y;
          }
          return x; 
      }
  }
  

  • 复杂度分析

    • 时间复杂度$O(n+maxlog(max)$假设数组中元素的最大值为$max$
    • 空间复杂度$O(max)$

• 优化将答案分为两部分

  • 子序列的长度为1此时最大公约数等于$nums[i]$对答案的恭喜为nums中不同元素的个数
  • 子序列的长度为2为了避免重复计算此时的最大公约数i必须不在nums中。此外如果最大公约数为$i$nums中最小要有$2i$和$3i$两个数因此i只需要枚举至$\frac{max}{3}$

  class Solution {
      public int countDifferentSubsequenceGCDs(int[] nums) {
          int ans = 0, mx = 0;
          for (int x : nums) mx = Math.max(mx, x);
          var has = new boolean[mx + 1];
          for (int x : nums)
              if (!has[x]) {
                  has[x] = true;
                  ++ans; // 单独一个数也算
              }
          for (int i = 1; i <= mx / 3; ++i) { // 优化循环上界
              if (has[i]) continue;
              int g = 0; // 0 和任何数 x 的最大公约数都是 x
              for (int j = i * 2; j <= mx && g != i; j += i) // 枚举 i 的倍数 j
                  if (has[j]) // 如果 j 在 nums 中
                      g = gcd(g, j); // 更新最大公约数
              if (g == i) ++ans; // 找到一个答案
          }
          return ans;
      }
  
      private int gcd(int a, int b) {
          while (a != 0) {
              int tmp = a;
              a = b % a;
              b = tmp;
          }
          return b;
      }
  }
  
  作者灵茶山艾府
  链接https://leetcode.cn/problems/number-of-different-subsequences-gcds/solutions/2061079/ji-bai-100mei-ju-gcdxun-huan-you-hua-pyt-get7/
  来源力扣LeetCode
  著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。