Can you solve the problem using hashtable or hashset?


  • 1
    J

    I use the hashset to solve the problem, but it caused Time limit exceed,can someone explain why ?Is bit manipulation the only way to accept ?Both two ways need O(n) run time.

    public class Solution {
    	public int singleNumber(int[] A) {
    		HashSet<Integer> set=new HashSet<Integer>();
    		for(int item:A){
    			if(set.contains(item)){
    				set.remove(item);
    			}
    			else
    				set.add(item);
    		}       
    		return set.iterator().next();
    	}
    }

  • 0
    C

    Here should be the answer instead of comments.
    I removed my comments to the right place.


  • 0
    C

    I met the same situation with you. My solution is exactly same to yours. If hashtable causes Time limit issue, why tag shows "Hash table"? Is there any other solutions related to the HashTable but satisfied with time limited?


  • 1
    C

    Because the exercise asks you to implement it without extra memory. But I am quite curiosity about the"Hash Table" lable of this question


  • 0
    C

    curiously my HashSet solution was accepted with instantiated an Iterator.

    public class Solution {
        public int singleNumber(int[] A) {
            HashSet<Integer> set = new HashSet<Integer>();
            Integer num, ans=0;
            for(int i=0; i<A.length; i++){
                num = new Integer(A[i]);
                if(!set.add(num)){
                    set.remove(num);
                }
            }
            Iterator setIterator = set.iterator();
            if(setIterator.hasNext()){
                ans=(Integer)setIterator.next();
            }
            return ans;
        }
    } 

  • 0
    B

    hash tables are way too slow (they incur a lot of cache misses). It's faster just to sort the input and run a simple algo on that than it is to do hash lookups.


  • 0
    E

    I used HashSet and got accepted.
    public int singleNumber(int[] nums) {
    HashSet<Integer> values = new HashSet<Integer>();
    for(int i = 0; i < nums.length; i ++){
    if(values.contains(nums[i])) values.remove(nums[i]);
    else values.add(nums[i]);
    }
    Iterator it= values.iterator();
    return (Integer)(it.next());
    }


  • 0

    It got AC now. Probably they modified the time limit.


Log in to reply
 

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