Java 中实现的 Ruby 的 flatten() 方法的算法

Question

我在读一本 Ruby 的书时遇到了一个函数 .flatten。因此，顾名思义，它将如下所示的数组展平：

a = [ 1, 2, 3 ]           #=> [1, 2, 3]
b = [ 4, 5, 6, [7, 8] ]   #=> [4, 5, 6, [7, 8]]
c = [ a, b, 9, 10 ]       #=> [[1, 2, 3], [4, 5, 6, [7, 8]], 9, 10]
c.flatten                 #=> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

我的问题是我正在尝试实现，看看我是否可以在 Java 中提出一个算法，这样当传递一个数组（可能包含）其他数组时，它将 return 数组。我不知道是否有更简单的方法来执行此操作，或者可能已经在 Java 中实现了它。无论如何，我知道我今天还没等到时间试一试 :)

这是我的算法开头：创建一个数组列表。

 for each element in array as x, 
   if x element, add to arrayList
else
  do a recurse(pass x as arg)

  Once done, create a int array with size = arrayList.
  Loop arrayList and add each element

到目前为止，这是我的代码：

public class Flatten {

public static void main(String[] args){
   a = [ 1, 2, 3 ]          
   b = [ 4, 5, 6, [7, 8] ] 
   c = [ a, b, 9, 10 ]       
   flatten(c);                 
}

public static int[] flatten(int[] a){
    ArrayList<Integer> ar = new ArrayList<Integer>();

    for(int i=0; i<a.; i
      Object o = a[i];  
        if(!obj instanceof Object[])){
          arr.add(a[i]);
   }

   else {
     int[] newArray = nR
      flatten(nR);
        }
     }     
  }

  int[] results = new int[ar.size()];

  for(int i=0; i<ar.size(); i++){
     int x = ar.get(i);
     int[i] = x;
  }

     return results;
  }

}

此算法的棘手部分是检查元素是否为数组。还有一个问题是 Java 中的数组应该用它们的大小来声明。

Answer 1

您可以编写一个方法，将多种 Object 扁平化为 List<Integer>，无论嵌套有多深。以下方法适用于 int[]、int[][]、Integer、Integer[]、Integer[][]、List<Integer>、List<List<Integer>>、List<int[]> 等（您可以轻松地将其设为 return 和 int[]）。

public static List<Integer> flatten(Object object) {
    List<Integer> list = new ArrayList<>();
    helper(object, list);
    return list;
}

private static void helper(Object object, List<Integer> list) {
    if (object instanceof Integer) {
        list.add((Integer) object);
    } else if (object instanceof int[]) {
        for (int a : (int[]) object)
            list.add(a);
    } else if (object instanceof Object[]) {
        for (Object obj : (Object[]) object)
            helper(obj, list);
    } else if (object instanceof Iterable) {
        for (Object obj : (Iterable) object)
            helper(obj, list);
    } else {
        throw new IllegalArgumentException();
    }
}

但是，这种事情真是个糟糕的主意。如果您发现自己编写了大量 instanceof 检查，然后根据结果做不同的事情，那么您很可能做出了一些糟糕的设计决定。

Answer 2

与ruby不同，java是一种静态类型语言。这意味着你不能真正在其中包含数组，它包含整数和数组作为元素（好吧，你可以 ...但你不应该）。

所以，在 java 中展平看起来像这样（我用列表来做，因为为了示例它更容易一些，但它是相同的想法）：

public static List<String>  flatten(List<List<String>> list) {
   List<String> result = new LinkedList<~>();
   for(List<String> l: list) result.addAll(l);
   return result;
}

Answer 3

您可能会发现实现 Iterator flatten(Object ... items) 更容易 - 返回正确大小的数组需要遍历所有条目两次（一次用于计数，一次用于填充）。 Iterator 可以利用 stack 并展平所有 Iterable，无论它们嵌套有多深。这样所有数组和所有 Collections 也会自然地变平。此外，阵列是如此 2014!!

这似乎有效。它利用 apache collections.IteratorUtils 在原始数组上创建迭代器。

private static class FlatteningIterator implements Iterator {

    // All fall to null at end.
    Object o;
    // It is an iterator.
    Deque<Iterator> stack = new LinkedList();
    // The next object to deliver.
    Object next;

    private FlatteningIterator(Object o) {
        this.o = o;
    }

    @Override
    public boolean hasNext() {
        // Keep looking until found one or exhausted
        while (next == null && (!stack.isEmpty() || o != null)) {
            if (o != null) {
                // Check o first.
                if (o instanceof Iterator) {
                    // Any kind of iterator?
                    stack.push((Iterator) o);
                } else if (o instanceof Iterable) {
                    // Any Iterable.
                    stack.push(((Iterable) o).iterator());
                } else if (o.getClass().isArray()) {
                    // Primitive array! Use apache IteratorUtils
                    stack.push(IteratorUtils.arrayIterator(o));
                } else {
                    // Just return the object.
                    next = o;
                }
                o = null;
            }

            // Still not found one?
            if (next == null) {
                // Get it from the current iterator?
                Iterator it = stack.peek();
                if (it != null) {
                    if (it.hasNext()) {
                        // Walk it.
                        o = it.next();
                    } else {
                        // Exhausted the iterator.
                        stack.remove();
                    }
                }

            }
        }
        return next != null;
    }

    @Override
    public Object next() {
        Object n = hasNext() ? next : null;
        next = null;
        return n;
    }

}

public static Iterator<Object> flatten(Object o) {
    return new FlatteningIterator(o);
}

public void test() {
    List<Object> test = new ArrayList<>();
    test.add("Hello");
    test.add(Arrays.asList(1, 2, new int[]{3, 6, 9, 12}, 4, 5));
    test.add("Bye");
    Iterator f = flatten(test);
    for (Object o : Iterables.in(f)) {
        System.out.print(o);
        if (f.hasNext()) {
            System.out.print(",");
        }
    }
    System.out.println();
}

Java 中实现的 Ruby 的 flatten() 方法的算法

Algorithm for Ruby's flatten() method implemented in Java

java

arrays

algorithm

object