My solution using a Bloom filter - O(n) time, O(1) memory


  • -1
    V

    Ok this may not be the most efficient in the case of an array of int (the real gain would be for a stream of int or strings), but I thought it could be a good way to try this concept.

    O(1) memory is actually pretty high here.

    public class Solution {
    	int hashes=5;
    	int bits=5000000;
    	int[] primes = {31, 37,  41,  43, 47, 53, 59, 61, 67, 71};
        
        public int findDuplicate(int[] nums) {
            
            boolean[] bitsMasks = new boolean[bits];
            for(int i=0; i<nums.length; i++){
            	int count=0;
                for(int h=0; h<hashes; h++){
                	String s =Integer.toString(nums[i]);
                    int hash = 0;
                    for(int c=0; c<s.length();c++)
                    	hash = primes[h]*hash + s.charAt(c);
                    hash =  hash % bits;
                    if(hash<0)
                    	hash = ( bits + hash) %bits;
                    if(!bitsMasks[hash])
                    	count++;
                    bitsMasks[hash]=true;
                }
                if (count==0)
                	return nums[i];
            }       
            return -1;
        }
    }

  • -5
    Z

    Definitely the best solution for industrial application.


  • 0
    S
    This post is deleted!

  • 2
    S

    Wrong solution. First of all, bloom filter is typically used to check non-existence of element; second, even if say we can tolerate some small false positive rate, that would require O(N) space.

    Your solution may fool leetcode OJ, but not a qualified interviewer.


  • 0
    F

    the best solution for an industrial application is to simply have a hashtable, and insert each element one at a time into the table. If the element is already there, return that element. However, that's O(n) space.


Log in to reply
 

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