6ms C++ O(n) Binary multiplicative hashing with linear probing


  • 0
    P
    class Solution {
    public:
    
        vector<int> twoSum(vector<int>& nums, int target) {
            random_device rd;
        	mt19937 gen(rd());
            unsigned int salt = gen();
            int numSize = nums.size();
            int hashBits = ceil(log2(numSize));
            int hashSize = exp2(hashBits);
            int hashShift = sizeof(int)*8 - hashBits;
            int hashTable[hashSize];
            int numIndex[hashSize];
            bool hashTableFill[hashSize] = {false};
            
            auto hashFunc = [&] (int value) -> int {
                int hashIndex = (unsigned int)value*salt >> hashShift; //Binary multiplicative hashing
                while(hashTableFill[hashIndex] && hashTable[hashIndex] != value) {
                    hashIndex++; // linear probing
                    if(hashIndex >= hashSize) hashIndex = 0;
                }
    			return hashIndex;
            };
            
            auto insert = [&] (int value, int index) {
                int hashIndex = hashFunc(value);
                hashTableFill[hashIndex] = true;
                hashTable[hashIndex] = value;
                numIndex[hashIndex] = index;
            };
            
            auto search = [&] (int value) -> int {
                int hashIndex = hashFunc(value);
                if(hashTableFill[hashIndex]){
                    return numIndex[hashIndex];
                } else {
                 	return -1;   
                }
            };
            
            vector<int> result(2);
            for(int i = 0; i<numSize; i++){
                int diff = target - nums[i];
                int searchID = search(diff);
                if(searchID>=0){
                    result[0] = searchID;
                    result[1] = i;
                    return result;
                }
                insert(nums[i], i);
            }
            return result;        
        }
    };
    

Log in to reply
 

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