假设我们有如下初始列表:
initial=[{"A",1}, {"A",2}, {"A",3}, {"B",5}, {"B",7}, {"C",6}, {"C",8}, {"D",4}]
是T的一个列表。我们有这样一个实体;class T{ string Title; int Id;}初始列表是按Title和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的列表，其中的元素按Title和Id排序，并返回一个新的T列表，该列表以每次从每个标题中提取一个实体的方式混合T实体。函数应该四舍五入每个Title，并从每个Title放置一个T实体(从A到D按升序四舍五入)，继续这样做，直到所有T实体都放置在结果列表中。
在O(N)中是否存在一个解，其中N是给定列表的大小?
-
首先让我们计算每个标题在初始列表中出现的次数。为此，可以遍历元素一次，每当遇到与最后一个元素相等的元素时，增加计数器的值，当遇到新元素时，将计数器的当前值压入新列表，并将计数器重置为1。因此，在这一步结束时，我们将得到一个看起来像这样的列表(例如:Count=[3,2,2,1])。
-
让我们对这个列表执行累加和，并将值存储在另一个pair列表中，每个pair的第一个元素是累加和，第二个元素初始化为0。现在我们有参照=[(3,0)、(5.0),(7,0)、(8,0)]。
-
现在让我们遍历这个列表，如果我们现在在这个列表的索引i中，我们将添加索引pref[i-1]的元素。First + pref[i]。第二个从初始数组到新数组，并增加pref[i]中的值。秒比1。处理完当前元素后，将新值复制到新列表中，除非pref[i]。秒= pref[i]。首先，然后我们不将其复制到新列表中。在下一次迭代中，我们以同样的方式处理新列表中的元素。
计算Count的第一个循环和参照需要O(N)时间，其中N为数组中元素的总数。在下一步中，我们需要遍历一个元素并复制它的总次数是N次，因为pref的每个元素将被处理和复制与其值相等的时间，并且值的总和是N元素的初始总数。因此整个算法的运行时间为O(N)。