3115. 质数的最大距离(中等)

Posted on In Views:

1，问题描述

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 * 105
  • 1 <= nums[i] <= 100
  • 输入保证 nums 中至少有一个质数。

2，初步思考

​ 感觉应该算作简单题才好，因为这个是使用双指针就可以解决掉了

3，代码处理

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
package questions;

import java.util.*;

public class _3115质数的最大距离 {

    // 双指针
    public int maximumPrimeDifference(int[] nums) {
        int i = 0, j = nums.length - 1;
        boolean[] flags = new boolean[2];
        while (i <= j) {
            if (!flags[0]) {
                if (isPrime(nums[i])) {
                    flags[0] = true;
                } else {
                    i++;
                }
            } else if (!flags[1]) {
                if (isPrime(nums[j])) {
                    flags[1] = true;
                } else {
                    j--;
                }
            } else {
                return j - i;
            }
        }
        return 0;
    }

    Set<Integer> primes = new HashSet<>(Arrays.asList(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));

    static List<Integer> primeList = new ArrayList<>();

    static {
        for (int i = 2; i <= 100; i++) {
            boolean flag = true;
            for (int j = 0; j < primeList.size(); j++) {
                if (i % primeList.get(j) == 0) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                primeList.add(i);
            }
        }
    }

    private boolean isPrime(int n) {
        int idx = Collections.binarySearch(primeList, n);
        return idx >= 0;
    }

    public static void main(String[] args) {
        _3115质数的最大距离 q = new _3115质数的最大距离();
        System.out.println(q.maximumPrimeDifference(new int[]{3, 5, 2, 4}));
    }
}