先看看題目:
204. Count Primes
Easy

Count the number of prime numbers less than a non-negative number, n.

Example:

Input: 10
Output: 4
Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.

簡單的說就是找出0 到 n整數以內有幾個質數,這一題我一開始自己寫是速度相當慢的,後來參考了別人的答案豁然開朗,其思路就是不要一個數一個數去徹底檢查,而是想辦法做出範圍內的查表,把範圍內被可以被小數字乘的數先找出來,歸類為非質數,每個數都用同張表去查,會省去相當多的時間,來看看程式碼:

class Solution {
    fun countPrimes(n: Int): Int {
        val notPrime = BooleanArray(n)
        var count = 0
        for (i in 2 until n) {
            if (notPrime[i] == false) {
                count++
                var j = 2
                while (i * j < n) {
                    notPrime[i * j] = true
                    j++
                }
            }
        }
        return count
    }
}

最後附上通關時間:

截圖 2020-09-01 上午11.58.39

arrow
arrow
    文章標籤
    LeetCode Kotlin
    全站熱搜
    創作者介紹
    創作者 Deyu 的頭像
    Deyu

    西瓜是肥貓

    Deyu 發表在 痞客邦 留言(0) 人氣()