寫在前面
這次周賽的第四題還是比較有意思的，尤其是時間復雜度方面讽膏，給的數(shù)據(jù)范圍在10^5檩电，需要O(NlogN)的算法，就很容易將思想局限在二分府树、排序俐末、堆、并查集奄侠，這些方法之中卓箫，而這道題復雜度的計算用到級數(shù)的概念，表面接近O(N ^ 2)的算法垄潮，實際復雜度為O(NlogN)烹卒，還是十分值得思考的一道題目。
題目
核心思路
這道題目使用暴力的解法顯然是不行的弯洗，單單是枚舉所有子序列都需要指數(shù)級別的時間復雜度甫题，而題目需要的算法為O(NlogN)，顯然會超時涂召。不過注意到給定數(shù)組中元素的大小范圍限定在[1, 200000]，給了這一限制敏沉，顯然是一個突破口果正。
所以不如直接枚舉 元素的值i ∈ [1, 200000]炎码，為了得到結(jié)果，就需要判斷當前元素i是否能作為某一個子序列的最大公約數(shù)秋泳。如果可以的話潦闲，這個子序列中的元素必然都能被i整除，例如：i, 2i, 4i, 5i, 9i迫皱，那么就可以枚舉i, 2i, 3i, 4i, ...并判斷其是否在數(shù)組中歉闰，然后將其加入到一個可能的子序列里，并求得這個子序列的最大公約數(shù)curGcd卓起，如果curGcd == i的話和敬，就代表枚舉到的i是滿足的，將答案加一即可戏阅。
這里需要承認的一個事實是：如果存在一個子序列a, b, c的最大公約數(shù)為i昼弟，那么新加入一個元素x，整個序列a, b, c, x的最大公約數(shù)應該為gcd(i, x)
有了這個事實奕筐，在求子序列的最大公約數(shù)時就可以每添加一個元素求解一次curGcd舱痘，然后判斷是否為目標值i即可，不需要維護這個枚舉的子序列了离赫。
完整代碼
class Solution {
public int gcd(int a, int b){
return a % b == 0 ? b : gcd(b, a % b);
}
public int countDifferentSubsequenceGCDs(int[] nums) {
boolean[] mark = new boolean[200001];
int maxNum = 0;
for(int num : nums) mark[num] = true;
int res = 0;
for(int i = 1; i < 200001; i++){
int curGcd = 0;
for(int j = i; j < 200001; j += i){
if(mark[j]){
if(curGcd == 0) curGcd = j;
else curGcd = gcd(curGcd, j);
if(curGcd == i){
res++;
break;
}
}
}
}
return res;
}
}
代碼也不難芭逝，就是根據(jù)上邊的思路維護一個結(jié)果res和當前子序列的最大公約數(shù)curGcd即可。比較難理解的就是算法的時間復雜度的計算了渊胸，看似時間為O(N ^ 2)旬盯，不過實際的復雜度應該為O(NlogN)，這里的N為數(shù)組元素的最大值蹬刷，代碼為了簡潔取了數(shù)據(jù)范圍峰值瓢捉，具體計算方法如下：
通過上述公式計算，總的時間復雜度應該為O(m * logm)办成，m代表數(shù)組元素的最大值泡态，是滿足題目要求的。
