algorithm - 二分搜索 + 排序与线性搜索（大 O）

Question

我有一个关于我正在处理的问题的问题。我必须随机播放视频而不重复视频。每个播放列表中的每个视频只能播放一次。每个视频都有一个从 0 到 max_video_count 的唯一 ID，该 ID 在运行时确定（取决于服务器）。

我现在要做的是，我创建了一个链接列表，其中添加了每个播放视频的唯一 ID。比我随机创建一个介于 0 和 max_video_count 之间的随机数，如果该数字已经在链表中，则进行线性搜索，如果是，我计算一个新数字..然后再次线性搜索..等等！

显然这不是很实用，有时需要很长时间才能找到一个元素。特别是当已经播放了很多视频时。

所以我想，我实现了二进制搜索而不是线性搜索，但这给我带来了我必须先对列表进行排序的问题。因此，我的下一步是思考，我在插入新的 unique_id 时对列表进行排序，而不是进行二分搜索。

我知道与 O(n) 线性搜索相比，二分搜索是 O(log n)，这是一个很大的进步。但是对列表进行排序也是 O(n)，因为要找到正确的位置，我必须再次进行线性搜索.....所以我找到了解决方案，而不是二进制搜索将 O(log N * n) 与O(n) 线性搜索 -> 快速线性搜索。是对的吗？也许我的整个方法都是错误的......但我还想不出更好的东西......

我对算法很陌生，所以如果有人能在这里启发我会很好:-)

问候马库斯

Answer 1

您本质上只是在查看随机排列。将您的视频排列在一个固定列表中，然后创建播放列表，生成该列表的随机排列并播放排列后的列表。

实现这种排列的一种典型且有效的 (O(n)) 方式是通过 Knuth Shuffle。

_{（实际上，您当然可以只创建索引集的随机排列，然后按排列索引的顺序播放项目。）}

Answer 2

如果视频的数量是固定的，您可以只使用一个布尔数组，全部初始化为 false，以跟踪已播放的内容 - 恒定时间查找。或者使用整数，计算播放次数，如果你想限制次数。

如果视频在播放过程中从列表中删除（或添加到），则用于跟踪已播放内容的关联数组（在某些语言中称为字典或哈希）可能更容易。

不要自己实现结构（除非这是您想要的学习练习），使用您选择的语言必须提供的内容。