代码之家  ›  专栏  ›  技术社区  ›  janvr

如果不使用这么多嵌套循环,如何在矩阵中找到数对?

  •  0
  • janvr  · 技术社区  · 7 年前

    我必须编写一个算法,在3D数组(嵌套列表)中找到两个数字,它们是:

    1. 在给定范围内(最小值<num1、num2、最大值)
    2. 不要重叠
    3. 尽可能接近值(abs(num1-num1)为 最小值)
    4. 如果存在更多满足1)的数字对, 2) 和3),选择总和最大的

    原始数据是一个N x N字段,由基本平方组成,每个平方中都有一个随机数。问题是找到两个子字段,其和满足所写的4个条件。我计算所有可能的和,并将它们存储在3D数组和[I][j][k]中,其坐标为起点(I,j)及其大小(k)。我需要跟踪索引,以确保字段不重叠。 现在,我正在使用6个嵌套for循环(每个索引一个,每个数字3个索引)和大量if语句(检查总和是否在范围内,字段是否重叠),然后简单地迭代每个可能的组合,这非常慢。

    有没有更快的方法(也许没有那么多循环)?仅允许使用标准库

    1 回复  |  直到 7 年前
        1
  •  0
  •   Centih    7 年前

    您可以检查下面列出的算法是否足够快。

    对3D数组中给定范围内的数字进行排序,并跟踪索引。 现在做一个嵌套循环,其中外部循环找到最小值的候选项,内部循环找到最大值的候选项。内部循环从列表中的下一个数字开始,当您找到与无重叠子字段相对应的数字(第一个满足条件2的数字,所有剩余的数字不符合条件3)或差值大于已找到的最佳数字对(该数字和所有剩余的数不符合条件3)时,内部循环即终止。当内部循环终止时,如果合适,请更新最佳候选对的信息。