Several Python solutions


  • 1
    C

    Easiest solution is to use an array to save all the nums[i] == target

        def __init__(self, nums):
            """
            
            :type nums: List[int]
            :type numsSize: int
            """
            self.nums = nums
            self.ret = []
            import random
    
        def pick(self, target):
            """
            :type target: int
            :rtype: int
            """
            i, count, length= 0, 0, len(self.nums)
            while i < length:
                if self.nums[i] == target:
                    self.ret.append(i)
                    count += 1
                i += 1
            return self.ret[random.randint(0,count-1)]
    

    The second solution is to use reservoir sampling

        def __init__(self, nums):
            """
            
            :type nums: List[int]
            :type numsSize: int
            """
            self.nums = nums
            import random
    
        def pick(self, target):
            """
            :type target: int
            :rtype: int
            """
            i, count, result= 0, 0, -1
            while i < len(self.nums):
                if self.nums[i] == target:
                    count += 1
                    if random.randint(0,count-1) == 0: result = i
                i += 1
            return result
    

    Although solution 2 use less memory than solution 1, it requires more time as multiple calls of randint

    Last solution, if you need to run pick function many times from an array with a large size, you need to scan the same array multiple times, that's inefficient. A better way is to use dict to save all the index of nums[i]. Or you can try to sort the nums and do binary search. Here I use dict.

        def __init__(self, nums):
            """
            
            :type nums: List[int]
            :type numsSize: int
            """
            self.listnums = collections.defaultdict(list)
            for i in range(len(nums)):
                self.listnums[nums[i]].append(i)
            import random
    
        def pick(self, target):
            """
            :type target: int
            :rtype: int
            """
            index = random.randint(0,len(self.listnums[target])-1)
            return self.listnums[target][index]
    

    HOWEVER, I got Memory Limit Exceeded error. Not sure why


  • 0
    P

    @cslns I also had the idea of preprocessing nums into a dict mapping each nums[i] to the indices where nums[i] appears. This gives an O(1) runtime for pick(), but an O(n) space requirement. While the problem is not clearly stated, it appears that the memory limit is such that we cannot use O(n) space. If we were optimizing for time instead of space, this would be the better approach.

    Given the problem statement, I don't think it would be valid to sort nums and do binary search, because sorting would change the indices.

    If the input array were already sorted, we wouldn't need to store all the indices, we would just need the first and last index of each nums[i]. In an array with no duplicates this would still be O(n) space, but it would save space in an array with duplicates.


Log in to reply
 

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