使用(x*y)的降序枚举2D平面上的网格点

Question

给定N > 0和M > 0,我想枚举所有(x,y)对,使得1 <= x <= N且1 <= y <= M,按(x*y)的降序排列.例如:给定N = 3且M = 2,枚举序列应为:

1. (3, 2) -- 3 * 2 = 6
2. (2, 2) -- 2 * 2 = 4
3. (3, 1) -- 3 * 1 = 3
4. (2, 1) -- 2 * 1 = 2
5. (1, 2) -- 1 * 2 = 2
6. (1, 1) -- 1 * 1 = 1

顺序(2, 1)和(1, 2)可以交换.一个显而易见的方法是将它们全部列出,插入到a中vector<pair<int, int> >,并std::sort()使用我自己的比较函数调用.但是,由于N和M可能很大,而且大多数时候我只需要序列的前几个项,我希望可以有一些更智能的方法来生成这样的序列而不是生成它们全部排序,需要尽可能多的N*M数组元素.

更新:我忘了提到虽然大部分时间我只需要前几个术语,但在枚举之前所需的术语数量是未知的.

Answer 1

如果您只是希望节省空间,同时保持时间大致相等,那么您可以指望每个连续较小的元素必须与其中一个元素相邻(在您提到的2-D网格中)你已经遇到过.(你可以用感应证明这一点,这并不是特别困难.我将假设其余的M> = N.)

基本算法看起来像:

Start with a list (Enumerated Points) containing just the maximum element, M*N
Create a max heap (Candidates) containing (M-1),N and M,(N-1).
Repeat this:
    1.Pick the largest value (x,y) in Candidates and append it to Enumerated Points
    2.Add (x-1),y and x,(y-1) to Candidates if they are not there already

只要您想要枚举点中的更多元素,就可以重复此操作.候选人的最大尺寸应该是M + N,所以我认为这是O(k log(M + N)),其中k是你想要的点数.

附录:避免重复的问题并不完全困难,但值得一提.我将在这个算法中假设你将网格放下,这样当你向下和向右移动时数字会下降.无论如何,它是这样的:

在算法的开头创建一个数组(列大小),每列有一个元素.您应该使此数组包含每列中的行数,这些行是枚举点列表的一部分.

添加新元素并更新此数组后,您将检查任一侧的列大小,以确定此新枚举点的右侧和下方的网格正方形是否已在候选列表中.

检查左侧列的大小 - 如果大于此列,则无需在新的枚举点下方添加元素.

检查右侧列的大小 - 如果它小于此列的相同大小,则不需要更新此列右侧的元素.

为了使这一点显而易见,让我们看看这个部分完成的图表,其中M = 4,N = 2:

4  3  2  1
*  *  *  2 |2
*  3  2  1 |1

元素(4,2),(3,2),(2,2)和(4,1)已经在列表中.(第一个坐标为M,第二个坐标为N.)"列大小"数组为[2 1 1 0],因为这是"枚举点"列表中每列中的项数.我们将要添加(3,1)到新列表 - 我们可以查看右侧的列大小,并得出结论:不需要添加(2,1),因为M = 2的列的大小更大比1-1.视觉上的推理非常清晰 - 当我们添加(2,2)时,我们已经添加了(2,1).