做法1
质数/素数,1不是质数。
思路:维护最小索引和最大索引,一次遍历后返回两者差值。
class Solution {
public:
bool isPrime(int num){
if (num == 2) return true;
else if (num == 1) return false;
for (int i = 2; i < num; i++){
if (num % i==0) return false;
}
return true;
}
int maximumPrimeDifference(vector<int>& nums) {
int min_idx = 300000, max_idx = -1;
for (int i = 0; i < nums.size(); i++){
if (isPrime(nums[i])){
min_idx = min(min_idx, i);
max_idx = max(max_idx, i);
}
}
return (max_idx - min_idx);
}
};
做法2
数据范围,nums[i]在100以内,可以直接枚举出100以内的质数,另外题目求的是索引的最大距离,因此找到第一个质数位置,后面找到新的质数位置直接用i-first即可。
class Solution {
public:
int maximumPrimeDifference(vector<int>& nums) {
unordered_set<int> primes = {
2,3,5,7,11,
13,17,19,23,29,
31,37,41,43,47,
53,59,61,67,71,
73,79,83,89,97
};
int n = nums.size();
int first = -1, ans = 0;
for (int i = 0; i < n; ++i) {
if (primes.count(nums[i])) {
if (first != -1) {
ans = max(ans, i - first);
}
else {
first = i;
}
}
}
return ans;
}
};
python
class Solution:
def maximumPrimeDifference(self, nums: List[int]) -> int:
primes = {
2, 3, 5, 7, 11,
13, 17, 19, 23, 29,
31, 37, 41, 43, 47,
53, 59, 61, 67, 71,
73, 79, 83, 89, 97
}
first, ans = -1, 0
for i, num in enumerate(nums):
if num in primes:
if first != -1:
ans = max(ans, i - first)
else:
first = i
return ans