从N个数中等概率打印M个数

从N个数中等概率打印M个数

问题

【题目】
给定一个长度为N且没有重复元素的数组arr和一个整数n，实现函数等概率随机打印arr中的M个数。

【要求】

1. 相同的数不要重复打印；
2. 时间复杂度为$O（M）$O（M），额外空间复杂度为$O（1）$O（1）；
3. 可以改变arr数组。
   
   

算法思路

不考虑额外空间复杂度为$O（1）$O（1）的限制，创建一个状态数组或者哈希表记录已打印的数。
本题的小技巧是与最后一个位置的数值交换swap arr[cur], arr[n - 1 - i]，很多有关等概率随机的题目沿用这个思路（e.g. 等概率随机快速获取key的结构）

相应代码

def random_print_m_numbers(arr, m):
    if arr is None or m <= 0 or len(arr) < m:
        return
    n = len(arr)
    for i in range(m):
        cur = int(random.random() * (n - i))
        print(arr[cur], end=' ')
        # swap arr[cur], arr[n - 1 - i]
        temp = arr[cur]
        arr[cur] = arr[n - 1 - i]
        arr[n - 1 - i] = temp

# 简单测试
if __name__ == '__main__':
    arr = [1, 4, 9, 3, 8]
    random_print_m_numbers(arr, 2)

有任何疑问和建议，欢迎在评论区留言和指正！

感谢您所花费的时间与精力！