<fieldset id="24wq0"></fieldset>

<ul id="24wq0"></ul>

leetcode54 Spiral Matrix

琛ｈ。發(fā)布于2019-08-16 10:37 / 3017人閱讀

摘要：題目要求按照順時針方向旋轉(zhuǎn)訪問數(shù)組中的元素思路一按行遍歷，轉(zhuǎn)化為因為不允許跳躍插入，也就是說如果插入的大于的，就會報出。思路二利用順序插入為了避免類型轉(zhuǎn)化帶來的不必要的性能下降，最好直接利用順序插入，一次遍歷數(shù)組。

題目要求

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

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].

按照順時針方向旋轉(zhuǎn)訪問數(shù)組中的元素

思路一：按行遍歷，array轉(zhuǎn)化為list

因為List不允許跳躍插入，也就是說如果插入的index大于list的size，就會報出IndexOutOfBoundException。所以這里我打算采取int[]數(shù)組先存儲值，再用Arrays.asList轉(zhuǎn)化成list。

    public List spiralOrder(int[][] matrix) {
         int row = matrix.length;
         if(row == 0){
             return new ArrayList();
         }
         int column = matrix[0].length;
         Integer[] result = new Integer[row*column];
         
         int prev = -1;
         int tempRow = row;
         int tempColumn = column;
         //按圈遍歷
         for(int i = 0 ; tempRow>1&&tempColumn>1 ; i++){
             
             //遍歷行
             for(int j = 0 ; j
但是在這個方法中，先利用int[]在轉(zhuǎn)化成List相當影響效率，雖說只需要遍歷n/2個數(shù)組。
思路二：利用List順序插入
為了避免類型轉(zhuǎn)化帶來的不必要的性能下降，最好直接利用List順序插入，一次遍歷int[][]數(shù)組。我們已知，除非特殊情況，每一圈必定都包含以下遍歷，順序的來說，就是從左往右遍歷，再從上往下遍歷，再從右往左遍歷，再從下往上遍歷。這時只需要從左往右遍歷的下標和從上往下的下標依次記錄了就行。
從左往右便利后，colBegin+1。從上往下遍歷后，rowEnd-1。這時需要判斷是否有往回遍歷的需要。從右往左遍歷后，colEnd-1。從下往上遍歷后，rowBegin+1。
代碼如下：
    public List spiralOrder2(int[][] matrix) {
         List res = new ArrayList();
        
        if (matrix.length == 0) {
            return res;
        }
        
        int rowBegin = 0;
        int rowEnd = matrix.length-1;
        int colBegin = 0;
        int colEnd = matrix[0].length - 1;
        
        while (rowBegin <= rowEnd && colBegin <= colEnd) {
            // Traverse Right
            for (int j = colBegin; j <= colEnd; j ++) {
                res.add(matrix[rowBegin][j]);
            }
            rowBegin++;
            
            // Traverse Down
            for (int j = rowBegin; j <= rowEnd; j ++) {
                res.add(matrix[j][colEnd]);
            }
            colEnd--;
            
            if (rowBegin <= rowEnd) {
                // Traverse Left
                for (int j = colEnd; j >= colBegin; j --) {
                    res.add(matrix[rowEnd][j]);
                }
            }
            rowEnd--;
            
            if (colBegin <= colEnd) {
                // Traver Up
                for (int j = rowEnd; j >= rowBegin; j --) {
                    res.add(matrix[j][colBegin]);
                }
            }
            colBegin ++;
        }
        
        return res;
     }

想要了解更多開發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號！將會不定期的發(fā)放福利哦~