文章/答案/技术大牛

发布

问螺旋矩阵算法
EN

Stack Overflow用户

提问于 2017-02-21 05:16:29

回答 1查看 518关注 0票数 0

我很难解释下面问题中的奇怪输入情况:给定一个m x n元素(m行，n列)的矩阵，以螺旋顺序返回矩阵的所有元素。

For example,
Given the following matrix:

[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]
You should return [1,2,3,6,9,8,7,4,5].

我的代码在所有较大的测试用例上都可以工作，但对于像这样的测试用例就失败了

[[6,9,7]]

我不确定如何构造我的代码来处理这些输入。有谁有主意吗？

def spiral_order(matrix)
    return nil if matrix.nil? 
    return [] if matrix.empty?
    m = matrix.length - 1
    n = matrix.first.length - 1
    start_col = start_row = 0 
    end_col = n
    end_row = m
    visited = []
    iter = 0
    until start_row > end_row && start_col > end_col
        until iter > end_col
            visited << matrix[start_row][iter]
            iter+=1
        end
        start_row += 1
        iter = start_row

        until iter > end_row
            visited << matrix[iter][end_col]
            iter += 1
        end
        end_col -= 1
        iter = end_col

        until iter < start_col
            visited << matrix[end_row][iter]
            iter-=1
        end
        end_row -= 1
        iter = end_row

        until iter < start_row 
            visited << matrix[iter][start_col]
            iter -= 1
         end
         start_col += 1
         iter = start_col
    end

    visited
end

在第6,9,7行，我得到了一个零错误。我知道整个循环运行了两次(这本身不应该是这种情况，因为我正在增加开始限制和减少结束限制)，但我正在努力创建既适用于常规输入又适用于奇怪情况的代码，而不会抛出大量条件来处理更多不常见的情况。

debugging

matrix

ruby

algorithm

回答 1

Stack Overflow用户

发布于 2017-02-21 06:49:59

这可以使用一组简单得多的代码来解决。从矩阵中剥离顶行，旋转矩阵，重复直到空。

def spiral_order(matrix)
  m = matrix.dup
  result = []
  until m.size < 1
    result << m.shift
    m = m.transpose.reverse
  end
  result.flatten
end

>> matrix = [[1,2,3],[4,5,6],[7,8,9]]
>> spiral_order(matrix)
=> [1, 2, 3, 6, 9, 8, 7, 4, 5]

>> matrix = [[6,9,7]]
>> spiral_order(matrix)
=> [6, 9, 7]

如果您正在处理大型矩阵，并且希望避免多个重复，为了增加一点复杂性，您可以这样做：

def spiral_order(matrix)
  m = matrix.map(&:dup)
  result = []
  until m.size < 1
    result << m.shift
    result << m.map(&:pop)
    result << (m.pop || []).reverse
    result << m.map(&:shift).reverse
  end
  result.flatten.compact
end

算法的工作原理是这样的:第2行深度复制矩阵，因此传入的原始矩阵不受影响。第5行去掉了第一行。第6行去掉了右列。第7行从最下面的一行中剥离并颠倒它。( || []确保我们不会对nil值调用#reverse。)第8行剥离了左列并颠倒了它。重复第5-8行，直到矩阵为空。此时，第10行删除内部数组和nils并返回结果。

票数 -1

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/42354355

复制

相似问题

问螺旋矩阵算法
EN

回答 1

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问螺旋矩阵算法EN

回答 1

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问螺旋矩阵算法
EN