algorithm - 对数千张 Chuck E. Cheese 门票进行排序

Question

我需要将一个 n 千大小的随机唯一正整数数组排序为连续整数组，每个组大小为 k 或更大，然后进一步分组为某个任意正整数 j 的股息。

换句话说，假设我在 Chuck E. Cheese 工作，我们有时会赠送免费门票。我有几十万张票在地板上，想找出员工发出了什么，但仅限于大于 500 的连续整数的票分组。每个员工都有一个从 0 到 100 的随机数分配给他们。该数字对应于分发的“批次”票证，即员工 1 分发的从 #000000 到 #001499 的票证，员工 2 分发从 #001500 到 #002999 的票证，依此类推。大量门票丢失或丢失。我只关心大于 500 的连续票号组。

我整理这堆东西的最快方法是什么？

编辑： 根据@trincot 的要求，这里有一个例子：

我在地板上有 150,000 张独特的票，范围从票 #000000 到 #200000（即从一堆随机票中丢失了 50,001 张）

第 1 步：使用introsort算法从小到大对每张票进行排序。

步骤2：逐一浏览票证列表，只收集“连续性”大于500的票证。即我记录我找到的连续值的数量，只保留那些连续值500或更高的票证。如果我有 #409 到 #909 的票，但没有 #408 或 #1000，那么我会保留该组，但如果该组错过了从 #409 到 #909 的任何票，我会扔掉该组并继续前进。

第 3 步：将我所有新排序的组组合在一起，每个组的大小为 500 或更大。

第 4 步：通过再次逐个查看最终数字，将每张票除以 1500，四舍五入到最接近的整数，然后将它们放入各自的堆中，每堆代表一名员工，从而找出属于谁的票。

最终结果是一堆堆，告诉我哪些员工一次发出了 500 多张票，他们这样做了多少次，以及他们用什么票。

带数字的样本：其中 k == 3 和 j = 1500；k 是最小连续整数分组大小，j 是最终票间隔分组大小，即 5,6，和 7 属于大小为 1500 的第 0 组间隔和 5996、5997、5998、5999 属于大小为 1500 的第三组间隔.

输入： [5 , 5996 , 8111 , 1000 , 1001, 5999 , 8110 , 7 , 5998 , 2500 , 1250 , 6 , 8109 , 5997]

输出：[ 0:[5, 6, 7] , 3:[5996, 5997, 5998, 5999] , 5:[8109, 8110, 8111] ]

标签： algorithmsortingmathmultidimensional-array

Answer 1

这是我能想到的最快方法的未经测试的 Python。对于找到的每个兴趣范围，它将只返回一对第一张/最后一张票。

def grouped_tickets (tickets, min_group_size, partition_size):
    tickets = sorted(tickets)
    answer = {}
    min_ticket = -1
    max_ticket = -1
    next_partition = 0
    for ticket in tickets:
        if next_partition <= ticket or max_ticket + 1 < ticket:
            if min_group_size <= max_ticket - min_ticket + 1:
                partition = min_ticket // partition_size
                if partition in answer:
                    answer[partition].append((min_ticket, max_ticket))
                else:
                    answer[partition] = [(min_ticket, max_ticket)]
            # Find where the next partition is.
            next_partition = (ticket // partition_size) * partition_size + partition_size
            min_ticket = ticket
            max_ticket = ticket
        else:
            max_ticket = ticket

    # And don't lose the last group!
    if min_group_size <= max_ticket - min_ticket + 1:
        partition = min_ticket // partition_size
        if partition in answer:
            answer[partition].append((min_ticket, max_ticket))
        else:
            answer[partition] = [(min_ticket, max_ticket)]

    return answer