[LeetCode] Challenge log 398

Posted on | Edited on |
398. Random Pick Index

https://leetcode.com/problems/random-pick-index/description/

Given an array of integers with possible duplicates, randomly output the index of a given target number. You can assume that the given target number must exist in the array.

Note:
The array size can be very large. Solution that uses too much extra space will not pass the judge.

Example:

1
2
3
4
5
6
7
8
int[] nums = new int[] {1,2,3,3,3};
Solution solution = new Solution(nums);

// pick(3) should return either index 2, 3, or 4 randomly. Each index should have equal probability of returning.
solution.pick(3);

// pick(1) should return 0. Since in the array only nums[0] is equal to 1.
solution.pick(1);
Solution:
  • space O(1), time O(n)
  • use 1 slot to hold output. if the n^th index is found, it has 1/n probability to replace the slot. (can use mutiple slot and the answer will be same)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
import random as rd
class Solution:
        
    nums = []
    
    def __init__(self, nums):
        """
        :type nums: List[int]
        """
        self.nums = nums
        
    def pick(self, target):
        """
        :type target: int
        :rtype: int
        """
        output = None
        count = 0
        for i in range(len(self.nums)):
            if self.nums[i] == target: 
                count += 1
                if output is None or rd.randint(1,count) == 1: 
                    output = i
                    
        if output is None: return None
        return output

# Your Solution object will be instantiated and called as such:
# obj = Solution(nums)
# param_1 = obj.pick(target)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
# first try, use two slots
import random as rd
class Solution:
        
    nums = []
    
    def __init__(self, nums):
        """
        :type nums: List[int]
        """
        self.nums = nums
        
    def pick(self, target):
        """
        :type target: int
        :rtype: int
        """
        can = []
        count = 0
        for i in range(len(self.nums)):
            if self.nums[i] == target: 
                count += 1
                if len(can) < 2: 
                    can.append(i)
                else:
                    temp = rd.randint(1,count)
                    if temp <= 2:
                        can[temp-1] = i
        if len(can) == 0: return None
        if len(can) == 1: return can[0]
        return can[rd.randint(0,1)]

# Your Solution object will be instantiated and called as such:
# obj = Solution(nums)
# param_1 = obj.pick(target)
0%