题目

Snail
蜗牛

描述

Snail Sort

Given an n x n array, return the array elements arranged from outermost elements to the middle element, traveling clockwise.

蜗牛排序

给定一个nxn数组，按顺时针方向返回从最外层元素排列到中间元素的数组元素。

如下面这个例子：

array = [[1,2,3],
     [4,5,6],
     [7,8,9]]
snail(array) #=> [1,2,3,6,9,8,7,4,5]

For better understanding, please follow the numbers of the next array consecutively:

为了更好地理解，请按照下一个数组的编号依次进行操作：

array = [[1,2,3],
     [8,9,4],
     [7,6,5]]
snail(array) #=> [1,2,3,4,5,6,7,8,9]

This image will illustrate things more clearly:

这幅图将更清楚地说明问题：

NOTE: The idea is not sort the elements from the lowest value to the highest; the idea is to traverse the 2-d array in a clockwise snailshell pattern.

注意：这个想法不是将元素从最低值排序到最高值；其思想是以顺时针蜗壳模式遍历二维阵列。

NOTE: The 0x0 (empty matrix) is represented as en empty array inside an array [[]].

注意：0x0（空矩阵）表示为数组[]中的en空数组。

思路

这道题乍一看，其实挺简单，不就是一圈一圈的往里走嘛，但是当我们细想，去循环遍历的时候，我们会发现我们会把自己一层一层的绕进入，需要考虑各种边界问题，以及循环的次数。

但是我们转念想一想，我们为啥要一直往里转了，大家通过图片可以看出，外面这一层和里面那一层的处理方法是否是一样的呢？

想到这里是不是想通了，是不是和递归的条件一样呢。既然里面那一层和外面这一层的处理方法是一样的，那么我们只要处理外面这一层，里面的交给递归去处理是不是就好了

好的，经过上面那一步的处理，是不是发现简单多了，我们再来简化一下，外层的处理是否可以依次分为四步处理：

• 上边界
• 右边界
• 下边界
• 左边界

每次处理我们只看我们处理的边界，是不是又变得简单了

但是因为测试例子的外层的大小都是不一样的，我们就需要考虑各种边界问题，上边界还好说，右边届的y从1开始，下边界的x从x - 1开始，左边界的y从y - 1开始到1，其实看起来挺麻烦，所以，为何我们不处理一个边界就删掉一个边界，那么是否就不需要开始具体是哪里，结束在哪里了。

完整代码

def snail(snail_map):
    # 保存结果
    result = []
    # 递归
    traversal(result,snail_map)
    return result
    pass

def traversal(result,array):
    # 终止条件
    if len(array) == 0:
        return
    # 上边界
    for i in array[0]:
        result.append(i)
    array.remove(array[0])
    # 注意1：这里存在的情况是，传入的array是一行的话，那么上面的操作删除的话，那么大小为0，如果没有这一步就会造成后面索引出界
    if len(array) == 0:
        return
    # 右边界
    for i in range(len(array)):
        result.append(array[i][-1])
        # 这样我们才能操作我们要删除的元素
        temp = array[i]
        # 注意2：这里不能使用remove删除，如果出现重复元素，会删除找到的第一个重复元素，但是我们要删除的是最后一个元素
        temp.pop()
        array[i] = temp
    # 下边界
    for i in range(len(array[0]) - 1,-1,-1):
        result.append(array[-1][i])
    array.remove(array[-1])
    #左边界
    for i in range(len(array) - 1,-1,-1):
        result.append(array[i][0])
        temp = array[i]
        temp.remove(temp[0])
        array[i] = temp
    traversal(result,array)