problem0398

README

398. Random Pick Index

题目

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:

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);

解题思路

见程序注释

Documentation

Index

• type Solution
  • func Constructor(nums []int) Solution
  • func (s *Solution) Pick(target int) int

Types

type Solution

type Solution struct {
	// contains filtered or unexported fields
}

Solution 是答案所需的数据结构

func Constructor

func Constructor(nums []int) Solution

Constructor 构建了 Solution

func (*Solution) Pick

func (s *Solution) Pick(target int) int

Pick 随机出现 target 在 nums 中的索引号