Why my golang solution using hash map got a wrong answer here ?


  • 0
    N

    I try to use hash map to solve the question. But it failed in big data test case.
    I use a map[int][]int to save the array. the key is the nums[i], value is an array of index.
    For example, for array 1 2 3 2 2 , the key 2 's value is 1 3 4.
    But this solution failed in big data test case.(can pass 8/13 test case.)
    I do not know what happened as my solution can run correctly in my PC.
    So can someone help me ?

    type Solution struct {
        m map[int][]int
    }
    
    
    func Constructor(nums []int) Solution {
        var s Solution
        s.m = make(map[int][]int)
        for i:=0;i<len(nums);i++{
            _,ok := s.m[nums[i]]
            if ok {
                s.m[nums[i]] = append(s.m[nums[i]],i)
            }else{
                s.m[nums[i]] = []int{i}
            }
        }
    	return s
    }
    
    
    func (this *Solution) Pick(target int) int {
        t,ok := this.m[target]
        if ok == false{
            return -1//cheat here
        }
        r := rand.Intn(len(t))
        return t[r]
    }
    

  • 0
    N

    I tried Reservoir Sampling But also failed in the same test case.

    type Solution struct {
        nums []int
    }
    
    
    func Constructor(nums []int) Solution {
        var s Solution
    	s.nums = nums
    	return s
    }
    
    
    func (this *Solution) Pick(target int) int {
    	idx,count := -1,0
    	for i:=0;i<len(this.nums);i++{
    		if this.nums[i] == target{
    			count ++ 
    			r := rand.Intn(count) + 1
    			if r== count{
    				idx = i
    			}
    		}
    	}
    	return idx
    }
    

Log in to reply
 

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