20ms C++ use bitmap


  • 9
    Z
    #define BITSPERWORD 32  
    #define SHIFT 5  
    #define MASK 0x1F  
    #define N 10000000  
    int a[1 + N/BITSPERWORD]; 
    void set_(int i) {        a[i>>SHIFT] |=  (1<<(i & MASK)); }  
    void clr(int i) {        a[i>>SHIFT] &= ~(1<<(i & MASK)); }  
    int  test(int i){ return a[i>>SHIFT] &   (1<<(i & MASK)); }  
      
     
    class Solution {
        
    public:
        bool containsDuplicate(vector<int>& nums) {
            if(nums.size()==0)return false;
            int i;  
        for (i = 0; i < nums.size(); i++)  
            clr(nums[i]);    
        for (i = 0; i < nums.size(); i++)  
        {
            if(test(nums[i]))return true;
            else set_(nums[i]);  
        }
       return false;
        }
    };

  • 2
    D

    what if nums[i] exceeds 10000000?


  • 0
    Z

    yes,if we use bitmap, it is a restriction that we must consider the limit of data
    If in the test case, there is a number no less than 10000000, the array will over flow.
    And, if the number set is 0,1,20000000, there will be lots of no used space, and the array will over flow.

    all these are the defect of bitmap


  • 0
    W

    Excellent ! You must be a reader of Programming Pearls


  • 0
    A

    Why don't you use int a[1 + N/BITSPERWORD] = {0} for cleaning it?


  • 0
    Y

    It seems that there is UB in you code.
    When the number is negative, i>>SHIFT is negative, so your code use negative index to access the array, resulting in undefined behavior.
    But it still works, so weird, I'm sure that there are negative numbers in the test cases.


Log in to reply
 

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