Given an input array that consists of numbers that may consist of duplicates, return the position of the number that is picked. This position has to be a “Random Pick Index” if the picked number has duplicates.

Example: Input: [1, 2, 4, 4, 4], Pick -> 4 then you can return 2, 3, or 4 randomly with equal probability. If 1 is the pick then 0 needs to be returned as there is only one occurrence at 0.

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 | /** * @param {number[]} nums */ var Solution = function(nums) { this.obj = {}; for (let i = 0; i < nums.length; i++) { if (this.obj[nums[i]] === undefined) this.obj[nums[i]] = []; this.obj[nums[i]].push(i); } }; /** * @param {number} target * @return {number} */ Solution.prototype.pick = function(target) { var dupes = this.obj[target].length; return dupes === 1 ? this.obj[target][0] : this.obj[target][Math.floor(dupes * Math.random())]; }; /** * Your Solution object will be instantiated and called as such: * var obj = new Solution(nums) * var param_1 = obj.pick(target) */ |