如何在之字形排序中找到ith项目？

Question

上周的一个问题是在n×m矩阵上定义了之字形排序,并询问如何按顺序列出元素.

我的问题是如何快速找到之字形排序中的第i项？也就是说,没有遍历矩阵(对于大的n和m来说太慢).

例如,如图所示n = m = 8,(x,y)描述(行,列)

f(0) = (0, 0)
f(1) = (0, 1)
f(2) = (1, 0)
f(3) = (2, 0)
f(4) = (1, 1)
...
f(63) = (7, 7)

具体问题:百万分之一矩阵的之字形排序中的第十亿(1e10)项目是什么？

Answer 1

1. 假设所需元素位于矩阵的上半部分.对角线的长度是1, 2, 3 ..., n.

2. 让我们找到所需的对角线.它满足以下属性: sum(1, 2 ..., k) >= pos但是sum(1, 2, ..., k - 1) < pos.总和1, 2, ..., k是k * (k + 1) / 2.所以,我们只需要找到的最小整数k这样k * (k + 1) / 2 >= pos.我们可以使用二分搜索或明确地解决这个二次不等式.

3. 当我们知道的时候k,我们只需要找到pos - (k - 1) * k / 2这个对角线的元素.我们知道它的起始位置和移动位置(向上或向下,取决于奇偶性k),因此我们可以使用简单的公式找到所需的单元格.

该解决方案有一个O(1)或一个O(log n)时间复杂度(这取决于我们是否使用二进制搜索或在步骤2中明确解决不等式).

如果所需元素位于矩阵的下半部分,我们可以解决此问题pos' = n * n - pos + 1,然后使用对称性来解决原始问题.

我在此解决方案中使用了基于1的索引,使用基于0的索引可能需要在某处添加+1或-1,但解决方案的想法是相同的.

如果矩阵是矩形而不是正方形,我们需要考虑这样一个事实:对角线的长度看起来是这样的:1, 2, 3, ..., m, m, m, .., m, m - 1, ..., 1(if m <= n)当我们搜索时k,所以总和变成了k * (k + 1) / 2if k <= m和k * (k + 1) / 2 + m * (k - m)other 之类的东西.