1. 问题

给定一个黑名单,包含[0, N)的一些数,从[0, N)之间的非黑名单数中随机采样一个值。

2. 思路

字典映射
(1)计算黑名单数的长度,记作B,因为已经排除掉了B个元素,所以最后是从N-B个数中采样。
(2)可以维护一个字典,表示从[0, N-B)到[0, N)之间的映射。
(3)这样就可以每次采样从[0, N-B)之间取,采样后将值映射回[0, N)。
(4)然而这么做爆内存了(MemoryError),因为N的最大长度为10亿,B的最大长度为10万,N-B特别大。

时间复杂度:O(N-B),空间复杂度:O(N-B),B表示blacklist的长度

(方法二)字典映射
(1)实际上我们不需要维护[0, N-B)中每个数的映射,我们只需要考虑[0, N-B)中的blacklist元素,因为只有这些元素才发生冲突。
(2)考虑换一种映射方法,因为是从[0, N-B)中采样,我们只需要考虑把[0, N-B)中的blacklist元素映射到[N-B, N)即可。
(3)而[N-B, N)中的blacklist元素是不需要(也不能)被映射的。我们只需要考虑那些[N-B, N)中不在blacklist中的元素,保证这些元素被映射就好了。
(4)所以我们只需要遍历[N-B, N)里面的B个元素,如果元素不在blacklist中,就建立一个映射,让blacklist中的元素(按顺序递增)指向它。
(5)这里判断元素是否在blacklist时,使用set效率会更高(一开始使用的list导致了超时)。映射时还是使用list的blacklist,因为要按顺序来映射。

时间复杂度:O(B * logB),空间复杂度:O(B),B表示blacklist的长度

3. 代码

字典映射

class Solution(object):
    def __init__(self, N, blacklist):
        """
        :type N: int
        :type blacklist: List[int]
        """
        B = len(blacklist)
        dic = {}
        offset = 0
        for i in range(N-B):
            if(i+offset not in blacklist):
                dic[i] = i + offset
            else:
                offset += 1
                dic[i] = i + offset
        self.dic = dic
        self.N = N-B

    def pick(self):
        """
        :rtype: int
        """
        i = random.randint(0,self.N-1)
        return self.dic[i]

(方法二)字典映射

class Solution(object):
    def __init__(self, N, blacklist):
        blacklist.sort()
        blacklist_set = set(blacklist)
        self.dic = {}
        self.M = N - len(blacklist)
        j = 0
        for i in range(self.M, N):
            if i not in blacklist_set:
                self.dic[blacklist[j]] = i
                j += 1

    def pick(self):
        i = random.randint(0,self.M - 1)
        return self.dic[i] if i in self.dic else i
内容来源于网络如有侵权请私信删除
你还没有登录,请先登录注册
  • 还没有人评论,欢迎说说您的想法!