leetcode 3115 题解

比较简单的一道题，思路也很清晰。

题目

给你一个整数数组 nums。
返回两个（不一定不同的）质数在nums中下标的最大距离。

示例 1：
输入： nums = [4,2,9,5,3]
输出： 3
解释： nums[1]、nums[3] 和 nums[4] 是质数。因此答案是 $|4 - 1| = 3$。

示例 2：
输入： nums = [4,8,2,8]
输出： 0
解释： nums[2] 是质数。因为只有一个质数，所以答案是 $|2 - 2| = 0$。

提示：
1 <= nums.length <= $3 \times 10^5$
1 <= nums[i] <= 100
输入保证 nums 中至少有一个质数。

思路

因为 1 <= nums[i] <= 100 ，所以可以直接枚举出数组中的所有素数，然后根据nums中的值来计算下标的最大距离。注意，1不是素数。

示例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    int maximumPrimeDifference(vector<int>& nums) {
        bool su[106];
        memset(su, true, sizeof(su));
        su[1] = false;
        for (int i = 4; i < 105; i++) {
            for (int j = 2; j <= sqrt(i); j++) {
                if (i % j == 0) {
                    su[i] = false;
                    break;
                }
            }
        }
        int gmin = 101, gmax = -1;
        for (int i = 0; i < nums.size(); i++) {
            if (su[nums[i]] == true) {
                if (i < gmin)
                    gmin = i;
                if (i > gmax)
                    gmax = i;
            }
        }
        return gmax - gmin;
    }
};
许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。