基于非唯一随机数生成唯一随机数：优化临时列表依赖问题

原函数get_d说明 #

原函数借助连续整数辅助列表，将非唯一随机数列表转换为唯一随机数列表：维护一个初始连续的整数列表，每次取列表中第r个元素加入结果，再删除该元素，以此保证结果的唯一性。

def get_d(rlist):
    # t[] 是0..n-1的整数列表，n足够大以避免删除操作出问题
    t  = list(range( len(rlist) + max(rlist) ))
    d  = []            # 待填充的输出列表
    for r in rlist:
        d.append(t[r]) # 将t中剩余的第r个元素加入d
        t.pop(r)       # 从t中删除该元素
    return d

示例：
get_d([3, 2, 3, 1, 5]) = [3, 2, 5, 1, 9]

需求与问题 #

需要移除对临时列表的依赖（避免超大数值场景下的内存占用），同时实现与get_d输出完全一致的功能。

自行实现的get_e存在边缘场景问题，比如测试用例[0,0,1,0,0]输出不匹配：

def get_e(r):
    e = []
    for i,t in enumerate(r):
        c = 0
        # 统计之前<=当前值的元素数量
        for j in range(i):
            if r[j] <= t:
                c+=1
        # 统计考虑虚拟删除后<=当前值的元素数量
        for j in range(i):
            if r[j] > t and r[j]-c <= t:
                c+=1
        e.append(t+c)
    return e

测试代码及结果：

for r in [ [3,2,3,1,5], [0,0,1,0,0]]:
    d = get_d(r)
    e = get_e(r)
    print('match:   ' if d==e else 'mismatch:', r, '  : ',  d, '  ', e)

输出：

match:    [3, 2, 3, 1, 5]   :  [3, 2, 5, 1, 9]    [3, 2, 5, 1, 9]
mismatch: [0, 0, 1, 0, 0]   :  [0, 1, 3, 2, 4]    [0, 1, 3, 3, 4]

解决方案 #

原get_d的核心逻辑是：每次从剩余的连续整数集合中选取第r个元素（索引从0开始）。要在无临时列表的情况下实现该逻辑，可通过维护已选元素的有序列表+二分查找计算每个元素的最终值：

对于当前的r_i，最终值x_i满足：x_i减去已选元素中小于等于x_i的数量，等于r_i（剩余元素中x_i的排名即为r_i）。通过二分查找可快速定位这个x_i，再将其加入有序列表供后续计算使用。

实现代码如下：

import bisect

def get_f(rlist):
    selected = []
    result = []
    for r in rlist:
        # 二分查找找到满足 x - bisect_right(selected, x) == r 的x
        low = r
        high = r + len(selected)  # 上限：最多有len(selected)个元素<=x
        while low < high:
            mid = (low + high) // 2
            cnt = bisect.bisect_right(selected, mid)
            if mid - cnt < r:
                low = mid + 1
            else:
                high = mid
        result.append(low)
        bisect.insort(selected, low)
    return result

测试验证：
运行原测试代码：

for r in [ [3,2,3,1,5], [0,0,1,0,0]]:
    d = get_d(r)
    f = get_f(r)
    print('match:   ' if d==f else 'mismatch:', r, '  : ',  d, '  ', f)

输出：

match:    [3, 2, 3, 1, 5]   :  [3, 2, 5, 1, 9]    [3, 2, 5, 1, 9]
match:    [0, 0, 1, 0, 0]   :  [0, 1, 3, 2, 4]    [0, 1, 3, 2, 4]

原理说明 #

1. 对于每个r_i，x_i的最小值是r_i（当所有已选元素都大于x_i时，x_i - 0 = r_i）。
2. x_i的最大值是r_i + len(selected)（当所有已选元素都小于等于x_i时，x_i - len(selected) = r_i → x_i = r_i + len(selected)）。
3. 通过二分查找在[low, high]范围内快速定位满足条件的x_i，单步时间复杂度为O(log k)（k为已选元素数量），整体时间复杂度为O(n log n)，远优于原get_d的O(n²)（pop(r)操作是O(n)），同时解决了超大数值场景的内存问题。

如果需要处理极大量数据，可使用**Fenwick树（二叉索引树）**替代二分查找，进一步优化查询和插入的时间复杂度，上述实现已能应对大部分场景且逻辑直观易懂。

内容的提问来源于stack exchange，提问作者fundamental