Java-使用递归展平数组

Question

我一直在练习算法，而递归总是我的弱点。此问题要求将嵌套数组平铺为单个数组。如果使用给定O（n^3）[给定相同大小的3d阵列]解决方案的循环，这将很简单。

然而随着递归，我一直在挣扎几个小时。这是我的，请注意我已经涉足了我的代码尝试不同的解决方案，这正是我决定留下来发布给你们。

我想什么是两件事情，反正是有解决我当前的代码，以获得正确的输出，并且是有使用递归，感谢写这个代码更简单，更混乱的方式！

奖金问题，如果我不知道嵌套阵列的尺寸，我将如何去了解这个问题，然后使用递归？

编辑 好了，所以经过一番硬编码（我不想做），我设法得到这个工作。但是，代码现在是硬编码，非常混乱，有无论如何清理代码或采用递归解决这个问题的简单方法吗？

EDIT2 我试图重做-ING使用helper方法递归这个问题。我去看看，如果我使用这种风格有更好的运气

import java.io. * ; 
    import java.util. * ; 
    class Solution { 
    // static int oneLen = 0; 
    //static int twoLen = 0; 
    //static int threeLen = 0; 

    static int oneCnt = 0; 
      static int twoCnt = 0; 
      static int threeCnt = 0; 
      static ArrayList <Integer> result = new ArrayList <Integer>(); 
      public static ArrayList <Integer> flatten(int [][][] arr){ 

    if (oneCnt < arr[threeCnt][twoCnt].length && !(oneCnt == 2 && twoCnt == 2 && threeCnt == 2)) 
    { 


    if (oneCnt == 0 && twoCnt == 0 && threeCnt == 0){ 
    result.add(arr[threeCnt][twoCnt][oneCnt]); 
      oneCnt++; 
      result.add(arr[threeCnt][twoCnt][oneCnt]); 
      System.out.println("Line One"); 
      System.out.println("Count1: " + oneCnt); 
      System.out.println("Count2: " + twoCnt); 
      System.out.println("Count3: " + threeCnt); 
    } 
    oneCnt++; 
      if (oneCnt != 3){ 
    result.add(arr[threeCnt][twoCnt][oneCnt]); } 






    System.out.println("Line One"); 
      System.out.println("Count1: " + oneCnt); 
      System.out.println("Count2: " + twoCnt); 
      System.out.println("Count3: " + threeCnt); 
      flatten(arr); 
    }  else if (oneCnt == arr[threeCnt][twoCnt].length && twoCnt < arr[threeCnt].length - 1){ 


    //oneLen = 0;  
    oneCnt = 0; 
      // twoLen++; 


      twoCnt++; 
      result.add(arr[threeCnt][twoCnt][oneCnt]); 
      System.out.println("Line Two"); 
      System.out.println("Count:1 " + oneCnt); 
      System.out.println("Count:2 " + twoCnt); 
      System.out.println("Count:3 " + threeCnt); 
      flatten(arr); 
    } 

    else if (oneCnt == arr[threeCnt][twoCnt].length && twoCnt == arr[threeCnt].length - 1 && threeCnt < arr.length - 1){ 

    oneCnt = 0; 
    twoCnt = 0; 
      threeCnt++; 
      result.add(arr[threeCnt][twoCnt][oneCnt]); 
      System.out.println("Line Three"); 
      System.out.println("Count:1 " + oneCnt); 
      System.out.println("Count:2 " + twoCnt); 
      System.out.println("Count:3 " + threeCnt); 
      flatten(arr); 
    } 
    return result; 
    } 
    public static void main(String[] args) { 
    int[][][] array = 
    { { {1, 2, 3}, { 4, 5, 6}, { 7, 8, 9} }, 
    { {10, 11, 12}, {13, 14, 15}, {16, 17, 18} }, 
    { {19, 20, 21}, {22, 23, 24}, {25, 26, 27} } }; 
      flatten(array); 
      for (int i = 0; i < result.size(); i++){ 
    System.out.print(result.get(i) + ","); 
    } 
    } 
    } 

输出：1,2,3,4,5,6,7,8,9,10,11,12,13,14,15 ，16,17,18,19,20,21,22,23,24,25,26,27，

EDIT3 使用的辅助递归我几乎有答案，但最后一个元素后不会添加到数组列表。

import java.io. * ; 
    import java.util. * ; 
    class Solution { 



    static ArrayList <Integer> result = new ArrayList <Integer>(); 
      public static void flatten(int [][][] arr){ 
    int oneLen = 0; 
      int twoLen = 0; 
      int threeLen = 0; 
      flattenHelper(arr, oneLen, twoLen, threeLen); 
    } 

    public static void flattenHelper(int [][][] arr, int oneLen, int twoLen, int threeLen){ 

    if (oneLen < arr[threeLen][twoLen].length - 1){ 
    System.out.println("Line One"); 
      System.out.println("Count:1 " + oneLen); 
      System.out.println("Count:2 " + twoLen); 
      System.out.println("Count:3 " + threeLen); 
      result.add(arr[threeLen][twoLen][oneLen]); 
      flattenHelper(arr, oneLen + 1, twoLen, threeLen); 
    } 
    else if (twoLen < arr[threeLen].length - 1){ 
    System.out.println("Line Two"); 
      System.out.println("Count:1 " + oneLen); 
      System.out.println("Count:2 " + twoLen); 
      System.out.println("Count:3 " + threeLen); 
      result.add(arr[threeLen][twoLen][oneLen]); 
      flattenHelper(arr, oneLen = 0, twoLen + 1, threeLen); 
    }  else if (threeLen < arr.length - 1){ 
    System.out.println("Line Two"); 
      System.out.println("Count:1 " + oneLen); 
      System.out.println("Count:2 " + twoLen); 
      System.out.println("Count:3 " + threeLen); 
      result.add(arr[threeLen][twoLen][oneLen]); 
      flattenHelper(arr, oneLen = 0, twoLen = 0, threeLen + 1); 
    } 

    } 

    public static void main(String[] args) { 
    int[][][] array = 
    { { {1, 2, 3}, { 4, 5, 6}, { 7, 8, 9} }, 
    { {10, 11, 12}, {13, 14, 15}, {16, 17, 18} }, 
    { {19, 20, 21}, {22, 23, 24}, {25, 26, 27} } }; 
      flatten(array); 
      for (int i = 0; i < result.size(); i++){ 
    System.out.print(result.get(i) + ","); 
    } 
    } 
    } 

输出：1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21 ，22,23,24,25,26，

Answer 1

它是递归的，你不需要改变输入结构，也不需要知道数组的维数。你可以去疯狂和混合阵列，列表和其他物体，它会返回一个ArrayList：

package stackOverflow; 

import java.lang.reflect.Array; 
import java.util.ArrayList; 
import java.util.List; 

public class Solution 
{ 
    public static void main(String[] args) { 
     int[][][] int3dArray = { { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } }, 
       { { 10, 11, 12 }, { 13, 14, 15 }, { 16, 17, 18 } }, 
       { { 19, 20, 21 }, { 22, 23, 24 }, { 25, 26, 27 }, { 28 }, { 29, 30 } } }; 
     String[][] string2dArray = { { "He, llo" }, { "Wo", "rld" } }; 
     String[] stringArray = { "Hello", "World" }; 
     Object[] objectArray = { "Hell", 0, "W", 0, "rld" }; 

     List<Object> mixList = new ArrayList<Object>(); 
     mixList.add("String"); 
     mixList.add(3); 
     mixList.add(string2dArray); 

     System.out.println(flatten(int3dArray)); 
     System.out.println(flatten(flatten(int3dArray))); 
     System.out.println(flatten(3)); 
     System.out.println(flatten(stringArray)); 
     System.out.println(flatten(string2dArray)); 
     System.out.println(flatten(objectArray)); 
     System.out.println(flatten(mixList)); 
    } 

    private static List<Object> flatten(Object object) { 
     List<Object> l = new ArrayList<Object>(); 
     if (object.getClass().isArray()) { 
      for (int i = 0; i < Array.getLength(object); i++) { 
       l.addAll(flatten(Array.get(object, i))); 
      } 
     } else if (object instanceof List) { 
      for (Object element : (List<?>) object) { 
       l.addAll(flatten(element)); 
      } 
     } else { 
      l.add(object); 
     } 
     return l; 
    } 
} 

它输出：

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30] 
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30] 
[3] 
[Hello, World] 
[He, llo, Wo, rld] 
[Hell, 0, W, 0, rld] 
[String, 3, He, llo, Wo, rld] 

这里有一个modified version，这也扁平化映射到值的集合。它可以输出Set或List。

这是我原来的解决方案，其中仅显示的结果，但返回无效：

package stackOverflow; 

import java.lang.reflect.Array; 


public class Solution 
{ 
    public static void main(String[] args) { 
     int[][][] array = { { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } }, 
       { { 10, 11, 12 }, { 13, 14, 15 }, { 16, 17, 18 } }, 
       { { 19, 20, 21 }, { 22, 23, 24 }, { 25, 26, 27 }, { 28 } } }; 
     flatten(array); 
    } 

    private static void flatten(Object object) { 
     if (object.getClass().isArray()) { 
      for (int i = 0; i < Array.getLength(object); i++) { 
       flatten(Array.get(object, i)); 
      } 
     } else { 
      System.out.print(object + ","); 
     } 
    } 
} 

它返回： 1,2,3,4,5,6,7,8,9,10 ，11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28，

Answer 2

如果你可以改变数据是整数，而不是为int数组，你可以检查传入数组的元素和递归对于那些数组中的元素，或只是将它们添加如果不是，则直接返回结果。

public static ArrayList<Integer> flatten(Object [] arr) { 
    ArrayList<Integer> result = new ArrayList<>(); 

    for (int i = 0; i < arr.length; i++) { 
     if (arr[i].getClass().isArray()){ 
      result.addAll(flatten((Object[])arr[i])); 
     } else { 
      result.add((int)arr[i]); 
     } 
    } 

    return result; 
}