如何从包含O(N)中排序子列表的给定列表中混合列表

Question

假设我们有如下的初始列表：

initial=[{"A",1}, {"A",2}, {"A",3}, {"B",5}, {"B",7}, {"C",6}, {"C",8}, {"D",4}]

它是T的一个列表，我们有一个类似的实体；class T{ string Title; int Id;}，最初的列表是按标题排序的，然后是Id，我们在开始时就知道了。

我想把这个列表混在一起，以便我们在最后有一个结果列表如下：

result=[{"A",1}, {"B",5}, {"C",6}, {"D",4}, {"A",2}, {"B",7}, {"C",8}, {"A",3}]

初始列表中的子列表是：

{"A",1}, {"A",2}, {"A",3}

{"B",5}, {"B",7}

{"C",6}, {"C",8}

{"D",4}

最初的问题可以是这样的:编写一个函数，其中包含按标题排序的T元素的列表，然后Id并返回一个新的T列表，它以一次从每个标题中抽取一个实体的方式混合T实体。函数应该围绕每个标题并在每个标题中放置一个T实体(从A到D的四舍五入)，继续这样下去，直到所有的T实体都被放在结果列表中。

在O(N)中是否有一个解，其中N是给定列表的大小？

Answer 1

首先，让我们计算一下每个标题在初始列表中出现多少次。当我们有一个等于最后一个元素的元素时，我们可以通过一次遍历元素并增加一个计数器，当我们到达一个新元素时，我们将计数器的当前值推到一个新列表中，并将计数器重置为1。

• 让我们对这个列表执行累积和，并将值存储在另一个对列表中，如果每对的第一个元素是累积和，第二个元素被初始化为零。现在我们有Pref=(3,0)，(5.0)，(7,0)，(8，0)，

。

• 现在让我们循环这个列表，如果我们现在在这个列表的索引I中，我们将在索引prefi-1处添加元素。首先，将初始数组中的prefi.second添加到新数组中，并将prefi.second中的值增加一个。在完成当前元素的处理之后，我们将该对的新值复制到一个新列表中，除非prefi.second = prefi.first，否则我们不会将其复制到新的列表中。在下一次迭代中，我们以相同的方式处理新列表中的元素。

计算Count和Pref的第一个循环需要O(N)时间，其中N是数组中元素的总数。在接下来的步骤中，我们需要对一个元素进行迭代并复制它的总次数是N次，因为pref的每个元素都将被处理和复制一个等于其值的时间，值的总和是N--元素的初始总数。因此，整个算法的运行时间为O(N)。