Skip to content

Latest commit

 

History

History
181 lines (99 loc) · 3.63 KB

0470._Implement_Rand10()_Using_Rand7().md

File metadata and controls

181 lines (99 loc) · 3.63 KB

470. Implement Rand10() Using Rand7()

难度: Medium

刷题内容

原题连接

内容描述

Given a function rand7 which generates a uniform random integer in the range 1 to 7, write a function rand10 which generates a uniform random integer in the range 1 to 10.

Do NOT use system's Math.random().

 

Example 1:

Input: 1
Output: [7]
Example 2:

Input: 2
Output: [8,4]
Example 3:

Input: 3
Output: [8,1,10]
 

Note:

rand7 is predefined.
Each testcase has one argument: n, the number of times that rand10 is called.
 

Follow up:

What is the expected value for the number of calls to rand7() function?
Could you minimize the number of calls to rand7()?

解题方案

思路 1 - 时间复杂度: O(1) or O(infinity)- 空间复杂度: O(1)******

Average 2*49/40 = 2.45 Call rand7 Per rand10

beats 66.53%

class Solution:
    def rand10(self):
        """
        :rtype: int
        """
        res = (rand7() - 1) * 7 + (rand7() - 1)
        while res >= 40:
            res = (rand7() - 1) * 7 + (rand7() - 1)
        return res % 10 + 1

思路 2 - 时间复杂度: O(1)- 空间复杂度: O(1)******

然后就是更优的一个思路，见lee215

Average 1.199 Call rand7 Per rand10

alexcheen says:

I think, rand7() gives log2(7) bits information, 
and rand10() need log2(10) bits information. so, in theory, it need call rand7() at least log7(10) times.

class Solution:
    def rand10(self):
        """
        :rtype: int
        """ 
        self.cache = []
        while not self.cache: 
            self.generate()
        return self.cache.pop()

    def generate(self):
        n = 19  # 1.199
        cur = sum((rand7() - 1) * (7**i) for i in range(n))
        rang = 7 ** n
        while cur < rang // 10 * 10:
            self.cache.append(cur % 10 + 1)
            cur //= 10
            rang //= 10

Follow up 1

Suppose we are given randM() which generates [1, 2, ..., M], we want to generate randN() which generates [1, 2, ..., N]. What would you do?

参考herokillerever

  • if N < M, then we can select 1, 2, ..., N, N+1, N+2, ..., M from randM(), as we know that [1, 2, ..., N] each with prob 1/M, since the algorithm terminates when the generated number less than N+1. Hence we have the uniform distribution.
  • M < N < M^2, then we can construct randM^2() = M * (randM()-1) + randM(), still we can select 1, 2, M, ..., N, N+1, N+2, ..., M^2, as we know that [1, 2, ..., N] each with prob 1/M^2, since the algorithm terminates when the generated number less than N+1. Hence we have the uniform distribution.
  • ......
  • The idea is that we can construct randM^n = M * (randM^(n-1)-1) + randM^(n-1) recursively. And then select accordingly.

Average 1.199 Call rand7 Per rand10

class Solution(object):
    def rand10(self):
        """
        :rtype: int
        """
        res = 11
        while res > 10:
            res = (rand7() - 1) * 7 + rand7()
        return res

Follow up 2

What if we have a rand(N) function which will generate [0, N] uniformly, and we want to return 0 1s, 1 2s, ... , N-1 Ns?

def get():
    a = rand(N)
    b = rand(N)
    if a + b < N:
        return a + b