Why I get TLE by using "vector<bool>"??? But "bool *" didn't??? And how about "vector<int>"???


  • 5
    1. vector<bool>
      ======

      int countPrimes(int n)
      {
      vector<bool> prime(n + 1, true);

       int sqrn = sqrt(n);
       for(int i = 2; i <= sqrn; ++ i)
           if(prime[i])
               for(int j = i * i; j < n; j += i)
                   prime[j] = false;
       
       int res = 0;
       for(int i = 2; i < n; ++ i)
           if(prime[i])
               ++ res;
       return res;
      

      }

    And I got "Time Limit Exceeded"

    1. bool *
      ======

    I changed "vector<bool>" to "bool *" and used new to alloc memory.

    I got "Accept".

    int countPrimes(int n)
    {
        bool *prime = new bool[n];
        for(int i = 0; i < n; ++ i)
            prime[i] = true;
        
        int sqrn = sqrt(n);
        for(int i = 2; i <= sqrn; ++ i)
            if(prime[i])
                for(int j = i * i; j < n; j += i)
                    prime[j] = false;
        
        int res = 0;
        for(int i = 2; i < n; ++ i)
            if(prime[i])
                ++ res;
                
        delete[] prime;
        
        return res;
    }
    

    And the question is: new operation is fast than alloc of vector???

    1. vector<int>
      ======

    I used "vector<int>" and bit manipulation. Maybe It can save some time.

    int countPrimes(int n)
    {
        int bit_num = sizeof(int) * 8;
        vector<int> prime(n / bit_num + 1, -1);
        
        int sqrn = sqrt(n);
        for(int i = 2; i <= sqrn; ++ i)
            if(prime[i / bit_num] & (1 << i % bit_num))
                for(int j = i * i; j < n; j += i)
                    prime[j / bit_num] &= ~(1 << j % bit_num);
        
        int res = 0;
        for(int i = 2; i < n; ++ i)
            if(prime[i / bit_num] & (1 << i % bit_num))
                ++ res;
        return res;
    }
    

    Also I got "Accept".

    1. vector<int> and hammingWeight
      ======

    I also used "vector<int>" and bit manipulation. And I got the number of 1 in each number by hammingWeight.

    int countPrimes(int n)
    {
        int bit_num = sizeof(int) * 8;
        vector<int> prime(n / bit_num + 1, -1);
        prime[0] &= ~3;
        
        int sqrn = sqrt(n);
        for(int i = 2; i <= sqrn; ++ i)
            if(prime[i / bit_num] & (1 << i % bit_num))
                for(int j = i * i; j < n; j += i)
                    prime[j / bit_num] &= ~(1 << j % bit_num);
        
        int res = 0;
        for(int i = 0; i < prime.size() - 1; ++ i)
            res += hammingWeight(prime[i]);
        for(int i = n / bit_num * bit_num; i < n; ++ i)
            if(prime[i / bit_num] & (1 << i % bit_num))
                ++ res;    
        return res;
    }
    int hammingWeight(int n)
    {
        int res = 0;
        while(n)
        {
            ++ res;
            n &= n - 1;
        }
        return res;
    }
    

    Also I got "Accept", and it fast than the upper one.


Log in to reply
 

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