java - 从外部元素到内部元素遍历数组

Question

我们正在做以下练习:Snail 。

为了能够完成该程序，我们考虑了以下示例:

给定数组:

[1, 2, 3, 1]
[4, 5, 6, 4]
[7, 8, 9, 7]
[7, 8, 9, 7]


1. Iterate over first row (i==0) j++
[0,0]=1, [0,1]=2, [0,2]=3, [0,3]=1

2. Traverse last column (j==array[i].length-1) i++
[1,3]=4, [2,3]=7, [3,3]=7

3. Iterate over last row (i==array.length-1) j--
[3,2]=9, [3,1]=8, [3,0]=7

4. Go up into first column, do not take first row (j==0) (0>i<array.length-1) i--
[2,0]=7, [1,0]=4

5. Iterate over second row, do not take the last column (i==1) (-1>j<array.length-2) j++
[1,1]=5, [1,2]=6

6. Get middle elements
[2,2]=9, [2,1]=8

我们编写了以下代码:

import java.util.*;
import java.util.stream.*;

public class Snail {
    public static int[] snail /*🐌🐚🔢*/ (int[][] array) {
      System.out.println("array: "+Arrays.deepToString(array));

      /*
      1. Iterate over first row (i==0) j++
      2. Traverse last column (j==array[i].length-1) i++
      3. Iterate over last row (i==array.length-1) j--
      4. Go up into first column, do not take first row (j==0) (0>i<array.length-1) i--
      5. Iterate over second row, do not take the last column (i==1) (-1>j<array.length-2) j++
      6. Do it and finally get the middle elements (i==2) (0<j<array[i].length-1)
      */

      List<Integer> firstRow = getRow(0,0,array[0].length,1,array);
      System.out.println("firstRow: "+Arrays.toString(firstRow.toArray()));

      List<Integer> lastColumn = getColumn(array[0].length-1,1,array[0].length,1,array);
      System.out.println("lastColumn: "+Arrays.toString(lastColumn.toArray()));

      List<Integer> lastRow = getRow(array.length-1,(array[array.length-1].length) - 2,-1,-1,array);
      System.out.println("lastRow: "+Arrays.toString(lastRow.toArray()));

      List<Integer> firstColumn = getColumn(0,array[0].length-2,0,-1,array);
      System.out.println("firstColumn: "+Arrays.toString(firstColumn.toArray()));

      List<Integer> middle = getRow(1,1,array[1].length-1,1,array);
      System.out.println("middle: "+Arrays.toString(middle.toArray()));


      List<Integer> middle2 = getRow(2,array[1].length-2,0,-1,array);
      System.out.println("middle2: "+Arrays.toString(middle2.toArray()));


      middle.addAll(middle2);
      firstColumn.addAll(middle);
      lastRow.addAll(firstColumn);
      lastColumn.addAll(lastRow);
      firstRow.addAll(lastColumn);
      System.out.println("firstRow: "+Arrays.toString(firstRow.toArray()));

      return firstRow.stream().mapToInt(i->i).toArray();
   }

   public static List<Integer> getRow(int row, int from, int to, int modifier, int[][] array){
     List<Integer> result = new ArrayList<>();

     for(int j=from; Math.max(j,to)>Math.min(j,to); j+=modifier){
       System.out.println("j: "+j);
       result.add(array[row][j]);
     }
     return result;
   }

   public static List<Integer> getColumn(int column, int from, int to, int modifier, int[][] array){
     List<Integer> result = new ArrayList<>();

     for(int j=from; Math.max(j,to)>Math.min(j,to); j+=modifier){
       System.out.println("j: "+j);
       result.add(array[j][column]);
     }
     return result;
   }

}

正如您所注意到的，我们已遵循这些步骤。但是，无论给定的数组大小如何，我们如何制定此解决方案？

目前发布的代码通过了第一个测试，但没有通过第二个测试(因此我们需要一种方法来回答所有可能的数组大小的这个练习):

import org.junit.Assert;
import org.junit.Test;
import org.junit.runners.JUnit4;
import java.util.Arrays;
import java.util.Random;
import static java.util.stream.Collectors.joining;

public class SnailTest {

  @Test
    public void SnailTest0() {
        int[][] array
                = {{1, 2, 3, 1},
                {4, 5, 6, 4},
                {7, 8, 9, 7},
                {7, 8, 9, 7}};
        int[] r = {1, 2, 3, 1, 4, 7, 7, 9, 8, 7, 7, 4, 5, 6, 9, 8};
        test(array, r);
    }

  @Test
    public void SnailTest1() {
        int[][] array
                = {{1, 2, 3},
                {4, 5, 6},
                {7, 8, 9}};
        int[] r = {1, 2, 3, 6, 9, 8, 7, 4, 5};
        test(array, r);
    }

 public String int2dToString(int[][] a) {
        return Arrays.stream(a).map(row -> Arrays.toString(row)).collect(joining("\n"));
    }

    public void test(int[][] array, int[] result) {
        String text = int2dToString(array) + " should be sorted to " + Arrays.toString(result);
        System.out.println(text);
        Assert.assertArrayEquals( result, Snail.snail(array));
    }

}

我们如何改进此算法以从外部元素到内部元素遍历数组？您将如何修改此算法以能够处理给定的任何数组大小？

Answer 1

您需要一个通用算法，可以为任何维度为 n, m 的给定数组打印您想要的内容。

这与您可以在互联网上随处找到的二维数组问题的螺旋打印非常相似。

下面是示例代码:

// declare n, m as number of rows and number of columns
// of the given matrix "array"

int startCol = 0, endCol = m - 1;
int startRow = 0, endRow = n - 1;

while(startRow <= endRow && startCol <= endCol) {
    for(int i = startCol; i <= endCol; i++) {
        System.out.println(array[startRow][i]);
    }
    for(int j = startRow + 1; j <= endRow; j++) {
        System.out.println(array[j][endCol]);
    }
    for(int i = endCol - 1; i >= startCol; i -= 1) {
        System.out.println(array[endRow][i]);
    }
    for(int j = endRow-1; j > startRow; j--) {
        System.out.println(array[j][startCol]);
    }

    startCol++;
    endCol--;
    startRow++;
    endRow--;
}