数组中等数之间的最大距离

Question

假设我有一个像这个例子的矩阵(数组),但更大:

0 0 5 0 3 6 6 4 0 3 0 8 0 1 1
9 4 0 6 0 0 0 4 1 0 6 0 7 0 0
3 1 6 1 5 0 8 0 8 0 3 2 6 4 8
1 0 2 2 8 5 8 1 8 7 4 1 0 3 0
6 3 8 1 0 0 4 0 0 3 1 5 2 0 0
0 0 5 0 3 6 6 4 0 3 0 8 0 1 1
9 4 0 6 0 0 0 4 1 0 6 0 7 0 0
3 1 6 1 5 0 8 0 8 0 3 2 6 4 8
1 0 2 2 8 5 8 1 8 7 4 1 0 3 0
6 3 8 1 0 0 4 0 9 4 1 5 2 0 0

我试图确定两个相等数字的位置,它们在阵列中的对角线,水平或垂直直线之间的距离最大,距离计算为它们之间的数字计数(距离d> = 0).

其他限制:

• 如上所述可以不包含被标记的开始和结束相同数目的,这样就可以不具有直线6 0 4 5 6 1 7 3 5 6和说距离6..6是8是有6顺序.
• 要查找的数字没有给出,但必须动态确定.

在示例中结果(将数组视为常规X | Y坐标系统,左下角为0,0)应确定P1(0,8),P2(8,0),d = 7(数字:9) ).

关于如何有效地做到这一点的任何好主意？我正在使用C#,但其他语言的示例/想法也很受欢迎.

如果你想知道这个问题来自哪里,我一直在思考各种与数学相关的挑战,我认为这些挑战很难解决(对我自己而言),并希望通过了解别人如何解决这些问题来更好地处理这些问题.谢谢!

Answer 1

算法:

简化问题.它相当于每行,列和对角线求解一维版本(在列表中找到相等值之间的最大间隙),然后返回最大值.

简化更多.一维版本非常简单.你只是建立其值映射到它们的位置列表的字典,解决"是什么位置该列表中的最大的三角洲"每个值,并返回最大的琐碎问题.

分析:

平凡的问题在位置列表的大小中占用线性时间(因为列表按[自然插入顺序]排序).因此,1-dim间隙问题在值列表的大小中占用线性时间(因为每个值有一个位置).因此,2-dim间隙问题需要矩阵大小的线性时间(因为每个值恰好包含在四个1-dim子问题中).

因此,如果矩阵是n m,则解决方案将花费O(n m)时间.它需要O(n + m)空间(在每个1-dim阶段存储值 - >位置字典).我真的怀疑你会做得更好(时间显然是最佳的,不太确定大小).