LeetCode 解題紀錄 2523. Closest Prime Numbers in Range

Closest Prime Numbers in Range - LeetCode

題目

給予兩個整數 left 與 right ，要求返回範圍內兩個最接近的質數，如果找不到，返回[-1,-1]

限制

• 1 ≤ left ≤ right ≤ 10⁶

觀察

• 找出範圍內的所有質數，並比對最接近的兩個質數差，屬於 Greedy 問題

解法(Math+Greedy)

• 使用 Sieve of Eratosthenes 演算法找出範圍內的質數

class Solution {
    public int[] closestPrimes(int left, int right) {
        int ans[] = new int[]{-1,-1};
        List<Integer> primes = genPrime(right);
        int min = Integer.MAX_VALUE, last = -1;
        for(int p:primes) {
            if(p>=left && p <= right) {
                if(last != -1) {                    
                    if(p-last < min) {
                        min = p-last;
                        ans[0] = last;
                        ans[1] = p;
                    }
                }
                last = p;
            }
        }
        return ans;
    }

    List<Integer> genPrime(int n) {
        boolean table[] = new boolean[n+1];
        for(int i=2;i<=Math.sqrt(n);i++) 
            if(!table[i]) 
                for(int j=i*i;j<=n;j+=i) 
                    table[j] = true;                                
        List<Integer> primes = new ArrayList();
        for(int i=2;i<=n;i++)
            if(!table[i])
                primes.add(i);
        return primes;
    }
}

結果

TC：O(n * log log n)，SC：O(n)