problem0710

package
v0.0.0-...-d3fc627 Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Feb 15, 2020 License: MIT Imports: 2 Imported by: 0

README

710. Random Pick with Blacklist

题目

Given a blacklistB containing unique integersfrom [0, N), write a function to return a uniform random integer from [0, N) which is NOTin B.

Optimize it such that it minimizes the call to system’s Math.random().

Note:

  • 1 <= N <= 1000000000
  • 0 <= B.length < min(100000, N)
  • [0, N)does NOT include N. See interval notation.

Example 1:

Input:
["Solution","pick","pick","pick"]
[[1,[]],[],[],[]]
Output: [null,0,0,0]

Example 2:

Input:
["Solution","pick","pick","pick"]
[[2,[]],[],[],[]]
Output: [null,1,1,1]

Example 3:

Input:
["Solution","pick","pick","pick"]
[[3,[1]],[],[],[]]
Output: [null,0,0,2]

Example 4:

Input:
["Solution","pick","pick","pick"]
[[4,[2]],[],[],[]]
Output: [null,1,3,1]

Explanation of Input Syntax:

The input is two lists:the subroutines calledand theirarguments.Solution'sconstructor has two arguments,N and the blacklist B. pick has no arguments.Argumentsarealways wrapped with a list, even if there aren't any.

解题思路

见程序注释

Documentation

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

Types

type Solution

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

Solution 包含了 BlackList 和 N

func Constructor

func Constructor(N int, blacklist []int) Solution

Constructor 构建了 Solution

func (*Solution) Pick

func (s *Solution) Pick() int

Pick 选取了不在 BlackList 中的值

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL