Обход массива от внешних элементов к внутренним

Question

Мы выполняем следующее упражнение: Улитка .

Чтобы завершить программу, мы подумали о следующем примере:

Учитывая массив:

[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

Довольно сложно написать правильный алгоритм, который работает для любого размера массива. Мы можем думать об этом как о рекурсивной проблеме, мы копируем внешние «слои» массива, а затем получаем меньший массив. Меньший массив имеет на 2 строки меньше и на 2 столбца меньше. Мы продолжаем повторять этот процесс, пока вложенный массив не будет пустым (с нулевыми строками или нулевыми столбцами). Вот мой код с парой тестов:

package com.stackoverflow;

import static org.junit.Assert.assertArrayEquals;

import org.junit.Test;

public class SnailTest {
  public static int[] snail(int[][] a) {
    return snail(a, 0, 0, new int[a.length * (a.length > 0 ? a[0].length : 0)], 0);
  }

  private static int[] snail(int[][] a, int row, int col, int[] result, int offset) {
    if (offset == result.length) {
      return result;
    }

    int height = a.length - 2 * row;
    int width = a[row].length - 2 * col;

    for (int i = 0; i < width; i++) {
      result[offset++] = a[row][col + i];
    }
    for (int j = 1; j < height - 1; j++) {
      result[offset++] = a[row + j][col + width - 1];
    }
    if (height > 1) {
      for (int i = width - 1; i >= 0; i--) {
        result[offset++] = a[row + height - 1][col + i];
      }
    }
    if (width > 1) {
      for (int j = height - 2; j > 0; j--) {
        result[offset++] = a[row + j][col];
      }
    }
    return snail(a, row + 1, col + 1, result, offset);
  }

  @Test
  public void test3x3() {
    assertArrayEquals(snail(new int[][] { //
        { 1, 2, 3 }, //
        { 8, 9, 4 }, //
        { 7, 6, 5 } }), //
        new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 });
  }

  @Test
  public void test4x4() {
    assertArrayEquals(snail(new int[][] { //
        { 1, 2, 3, 4 }, //
        { 12, 13, 14, 5 }, //
        { 11, 16, 15, 6 }, //
        { 10, 9, 8, 7 } }), //
        new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16 });
  }
}

Answer 2

Вам необходим универсальный c алгоритм, который может печатать, что вы хотите, для любого данного массива, имеющего размеры n, m.

Это очень похоже на спиральную печать задачи двумерного массива, которую вы можете найти где-нибудь на inte rnet.

Вот пример кода:

// 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--;
}