Re: [閒聊] 每日leetcode
https://leetcode.com/problems/closest-prime-numbers-in-range
2523. Closest Prime Numbers in Range
給你兩個數字left和right，找出兩個數字介於left和right，兩者數字不同且是質數，這
兩個數字的差需要最小，如果有多個一樣的差則取nums1比較小的，找不到返回{-1,-1}。
思路:
1.先算出到right為止的所有質數
2.把質數兩兩匹配，然後取最小且最早出現的一對
Java Code:
-------------------------------------------------------
class Solution {
public int[] closestPrimes(int left, int right) {
boolean[] notPrime = new boolean[right + 1];
notPrime[1] = true;
for (int i = 2; i <= right; i++) {
if (notPrime[i]) continue;
int curr = i + i;
while (curr <= right) {
notPrime[curr] = true;
curr += i;
}
}
Integer num1 = null;
Integer num2 = null;
int[] res = null;
for (int i = left; i <= right; i++) {
if (!notPrime[i]) {
if (num1 == null) {
num1 = i;
} else if (num2 == null) {
num2 = i;
res = new int[]{num1, num2};
} else {
if (res[1] - res[0] > num2 - num1) {
res[0] = num1;
res[1] = num2;
}
num1 = num2;
num2 = i;
}
}
}
if (num1 != null && num2 != null) {
if (res[1] - res[0] > num2 - num1) {
res[0] = num1;
res[1] = num2;
}
return res;
}
return new int[]{-1, -1};
}
}
-------------------------------------------------------
--
https://i.imgur.com/ZfdGodg.jpeg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 49.158.101.161 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1741354512.A.55A.html
※ 編輯: Rushia (49.158.101.161 臺灣), 03/07/2025 21:39:03
討論串 (同標題文章)
完整討論串 (本文為第 1360 之 1552 篇)：