我怎样才能在线性时间内打乱一个数组而不让重复的元素彼此相邻？

Question

例如：

T = [b, c, b, b, a, c] #each element represents questions related to topics a, b, c

我想要的是确保没有来自同一主题的 2 个问题彼此相邻。（见 T，其中 b、b 彼此相邻）

所以我想重新排列 T，使得属于同一主题的两个问题不会彼此相邻，即 Tnew = [b, c, b, a, b, c]

但条件是我们必须在线性时间内完成它，即 O(n) 或 (n) 的 Big-O

The algorithm that I thought of:

1)Create a dict or map to hold the occurrence of each topics:
a --> 1
b --> 3
c --> 2

2) Now based on the counts we can create new array such that:
A = [a, b, b, b, c, c]

3) Now perform unsorting of Array which I believe runs in O(n).
(unsorting is basically find midpoint and then merge the elements alternately from each half.

有人可以帮我设计一个伪代码或算法，可以更好地处理具有 k 个主题的任何输入吗？

这是我准备考试的随机题。

Answer 1

有一个时间复杂度的线性方法 O(log c * n)，其中 c 是唯一项目的数量，n 是项目的总数。

它的工作原理如下：

创建项目的频率 table。这只是一个元组列表，说明每个项目有多少可用。让我们将列表中的元组存储为 (quantity, item)。这一步是O(n)。您可以在 python 或 collections.defaultdict(int) 中使用 collections.Counter 或香草 dict.
堆化最大堆中的元组列表。这可以在 O(n) 中完成。这个堆的前面有数量最多的项目。您可以在 python 中使用 heapq 模块。我们称这个堆为 hp.
有一个名为 res 的结果列表。
现在运行一个循环while len(hp) > 0:并按如下方式做：

从堆中弹出 2 个最大的元素。 O(log c)操作。
每人加一到 res。确保正确处理极端情况（如果有）。
减少两个项目的数量。如果他们的 quantity > 0 将他们推回堆上。 O(log c)操作。

最后，你可以用一件没有对等物进行交织的物品来结束。如果一个项目的数量大于所有其他项目的数量总和，就会发生这种情况。但没有办法解决这个问题。您的输入数据必须遵守此条件。

关于时间复杂度的最后一点说明：如果唯一项的数量是常数，我们可以从时间复杂度中删除 log c 因素并认为它是线性的。这主要是我们如何定义事物的案例。

Answer 2

这是 O(n) 解决方案（部分灵感来自@user1984 的回答）：

假设您知道每个元素要插入多少个，并且已经对这些计数进行了排序。假设我们随后决定通过递增地交错元素组来构建解决方案。我们从频率最低的一组元素 G0 开始。然后，我们取下一个最受欢迎的组 G1，并将这些值交织到我们现有的列表中。

如果我们继续这种方式，我们可以遵守一些规则：

如果当前组G的元素比所有更小的组的元素加起来还多加一，那么：
- 结果将有 G 的元素彼此相邻
- 无论其先前状态如何，较小组中的元素都不会彼此相邻（inter-group 或 intra-group）
否则
- 结果将没有 G 的元素彼此相邻
无论如何，如果放置得当，G 包含的元素足以分隔下一个最小组 G-1 的各个元素。

考虑到这一点，我们可以（递归地）看到，只要我们将交织转移到与任何未解决的邻居违规重叠，我们就可以保证只要 G 的元素少于较小的组加二的元素，总体结果绝对不会有任何邻居违规。

当然，我上面概述的计算逻辑会带来一些性能问题，因此我们将以稍微不同但等效的方式计算相同的结果。相反，我们将先插入最大的组，然后逐渐缩小。

首先，创建一个频率table。您需要形成一个 item: quantity 映射，因此类似于 python 中的 collections.Counter()。这需要 O(N) 时间。

接下来，按频率对映射进行排序。这可以使用计数排序在 O(N) 时间内完成，因为所有元素都是整数。注意有 c 个元素，但是 c <= N，所以 O(c) 是 O(N).

之后，建立一个长度为N的链表，节点值从[0, N)开始（升序）。这将帮助我们跟踪接下来要写入哪些索引。

对于我们有序映射中的每个项目，从 0 迭代到关联的计数（不包括）。每次迭代，从链表中移除当前元素（（重新）从头开始），并在链表中向前遍历两个节点。将 item/number 插入目标数组中每个已删除节点的索引处。这将花费 O(N) 时间，因为我们遍历每个项目约 2k 个节点（其中组大小为 k），并且所有组的总大小为 N，因此 2N遍历。每次移除可以在O(1)时间内执行，所以O(N)用于遍历和移除。

所以总而言之，这将花费 O(N) 时间，利用链表、散列 tables（或某种 O(1) 访问映射）和计数排序。

Answer 3

collections 模块可以提供帮助。使用 Counter 可以让您在 O(n) 时间内出现每个问题的次数。将它们转换为 deque 中的迭代器将允许您按顺序交错问题，但您需要按出现的降序处理它们。按频率顺序获取计数器通常需要一种排序，即 O(nLogn)，但您可以使用鸽巢方法在 O(n) 时间内按公共频率对迭代器进行分组，然后以相反的顺序遍历这些组频率。不同频率的最大数量是已知的，将小于或等于√(0.25+2n)-0.5，小于 O(n)。

最多有 n 个迭代器，因此构建双端队列的时间 <= O(n)。通过迭代器直到耗尽最多需要 2n 次迭代：

T= ['b', 'c', 'b', 'b', 'a', 'c']

from collections import Counter,deque
from itertools import repeat
    
result = []
counts = Counter(T)                             # count occurrences O(n)
common = [[] for _ in range(max(counts.values()))]    # frequency groups
for t,n in counts.items():                            
    common[n-1].append(repeat(t,n))                   # iterators by freq.
Q = deque(iq for cq in reversed(common) for iq in cq) # queue iterators
while Q:                                        # 2n iterations or less
    iq = Q.popleft()          # O(1) - extract first iterator
    q = next(iq,None)         # O(1) - next question
    if not q: continue        #      - exhausted, removed from deque
    result.append(q)          # O(1) - add question to result
    Q.insert(1,iq)            # O(1) - put back iterator as 2nd

print(result)
['b', 'c', 'b', 'c', 'b', 'a']

我怎样才能在线性时间内打乱一个数组而不让重复的元素彼此相邻？

How can I scramble an array in linear time without having duplicate elements next to one another?

python

algorithm

sorting

computer-science