题解 | #能被多个质数整除的第K长子段#
能被多个质数整除的第K长子段
http://www.nowcoder.com/practice/162f79e68d6c4b9988a994344181d366
算法思想一：暴力法
解题思路：
根据题意：
1、首先我们准备了2到数组最大值中的所有质数，记录到primes中。
2、然后暴力遍历每一个数对&preview=true)
，每次对于数对区间中的元素，对每一个primes中的质数，查看是否能整除区间中所有的元素，如果可以计数加1，当计数不小于
时，就可以记录这对数对。
3、然后重载sort函数的比较，使其排序时按照
的大小来排序
3、然后重载sort函数的比较，使其排序时按照
这样就可以直接在排好序的数组中找到第
大的数对
图解：
代码展示：
C++版本
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* 求满足条件的第K大长度
* @param A int整型vector 牛牛的数组A
* @param X int整型 至少要存在X个不同的质数
* @param K int整型 牛牛希望找到第K大的长度
* @return int整型
*/
static bool comp(pair<int, int>& a, pair<int, int>& b){ //重载比较，按区间大小排序
return a.second - a.first < b.second - b.first;
}
int GetKthLength(vector<int>& A, int X, int K) {
// write code here
int maxnum = *max_element(A.begin(), A.end()); //取数组最大数
int n = A.size();
vector<int> primes; //记录小于最大值的所有质数
vector<int> notPrime(maxnum + 1, 0); //辅助数组，运算质数的时候用
notPrime[1] = 1;
for(int i = 2; i <= maxnum; i++){ //遍历到最大值，找到所有质数
if(!notPrime[i]) //非合数
primes.push_back(i);
for(int j = 0; j < primes.size() && i * primes[j] <= maxnum; j++)
notPrime[i * primes[j]] = 1; //这是合数
}
vector<pair<int, int> > leftRight; //记录左右区间
for(int i = 0; i < n; i++){ //遍历所有数对
for(int j = i; j < n; j++){
int count = 0; //统计能整除全部区间内元素的质数个数
for(int k = 0; k < primes.size(); k++){
bool flag = true;
for(int x = i; x <= j; x++){
if(A[x] % primes[k] != 0){ //不能整除，这个质数不计算了
flag = false;
break;
}
}
if(flag) //所有整除计数加1
count++;
}
if(count >= X) //质数个数不小于X
leftRight.push_back(make_pair(i, j));
}
}
sort(leftRight.begin(), leftRight.end(), comp); //按照区间大小排序
int m = leftRight.size();
if(m < K)
return -1;
return leftRight[m - K].second - leftRight[m - K].first + 1; //返回第K大
}
}; 复杂度分析
时间复杂度：%5E2)&preview=true)
，其中n为数组A的长度，m为质数数组的长度，找到所有的质数最坏遍历两层到数组A的最大值，后续嵌套了四层循环，排序和找最大值函数相对较小，可忽略。
空间复杂度：)&preview=true)
，多个辅助数组
算法思想二：方法一改进
解题思路：
方法一嵌套循环太多，复杂度较高1、计算质数数组的时候就可以找到
2、然后排除质因数达不到的元素
3、然后可以根据子段的最大公约数来计算，最大公约能够被不小于个质数整除即可
4、可以从
到
最长段开始找，利用二分思想找到第大
代码展示：
C++版本
class Solution {
public:
//依据长度，计算有多少个质因数，从x到结尾
int CountMoreThanX(int x, vector<bool>& isOk, vector<vector<pair<int, int>>>& gcd){
int s = 0, n = gcd.size();
for(int i = 0; i < n; i++){ //遍历寻找共同的质因数个数
for(int j = 0; j < gcd[i].size() - 1; j++){
if(!isOk[gcd[i][j].second])
break;
int len0 = i - gcd[i][j].first + 1, len1 = i - gcd[i][j + 1].first;
if(len0 >= x)
s += (len1 - len0 + 1);
else if(len1 >= x)
s += (len1 - x + 1);
}
}
return s;
}
int GetKthLength(vector<int>& A, int X, int K) {
int maxnum = *max_element(A.begin(), A.end()); //取数组最大数
int n = A.size();
vector <int> nums(maxnum + 1, 0); //统计每个数质因数个数
vector <int> notPrime(maxnum + 1, 0); //记录某个数是否是质数
vector <int> primes; //质数数组
nums[1] = 0;
nums[2] = 1;
notPrime[1] = 1;
for(int i = 2; i <= maxnum; i++){//遍历到最大值，找到所有质数
if(!notPrime[i]){//非合数
primes.push_back(i);
nums[i] = 1;
}
for(int j = 0; j < primes.size() && i * primes[j] <= maxnum; j++){
int p = primes[j];
notPrime[i * p] = 1; //这是合数
if(i % p == 0){ //因数的个数
nums[i * p] = nums[i];
break;
}else
nums[i * p] = nums[i] + 1;
}
}
vector<bool> isOk(maxnum + 1, false);
for(int i = 2; i <= maxnum; i++) //有不小于x个质因数的才标记为1
isOk[i] = (nums[i] >= X);
vector<vector<pair<int, int> > > gcd(n);
for(int i = 0; i < n; i++){
gcd[i].push_back(make_pair(i, A[i]));
if(i > 0){
for(auto pre : gcd[i - 1]){
int curgcd = __gcd(A[i], pre.second); //计算前后两个数的最大公约数
if(curgcd != gcd[i].back().second) //公约数不等于后面来的数
gcd[i].push_back(make_pair(pre.first, curgcd)); //加入前面的数
}
}
}
for(int i = 0; i < n; i++)
gcd[i].push_back(make_pair(-1, 0));
if(CountMoreThanX(1, isOk, gcd) < K) //数对数量小于K
return -1;
int l = 1, r = n;
while (l < r) { //二分法找第k大
int mid = l + ((r - l + 1) / 2);
if (CountMoreThanX(mid, isOk, gcd) < K)
r = mid - 1;
else
l = mid;
}
return l;
}
}; 复杂度分析
时间复杂度： 空间复杂度：)&preview=true)
，多个辅助数组
