Any one has AC HashTable solution?


  • 0
    H
    public class Solution {
        public int countPrimes(int n) {
            if (n <= 2) return 0;
            Set<Integer> set = new HashSet<Integer>();
            for (int i = 2; i < n; i++) {
                set.add(i);
            }
            
            int m = (int)(Math.sqrt(n));
            for (int i = 2; i <= m; i++) {
                if (set.contains(i)) {
                    for (int j = i * i; j < n; j += i) {
                        set.remove(j);
                    }
                }
            }
            return set.size();
        }
    }
    

    There's a Hash Table tag under this question, but my code here got TLE. I think .add() and .remove() cost too much time. How can I improve it? If you have an AC solution, please post it. Thanks.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.