Java: Чередование нескольких массивов в один массив

Question

Я нашел похожий вопрос о чередовании двух массивов в один, но в PHP.Мне также задавали этот вопрос в интервью, но я не смог его решить, вернулся в SO, чтобы посмотреть, был ли он уже решен, но я смог найти только эту бумагу

Так что любые указателипсевдокод или определение метода?

Большие (O) ограничения: O (n) - затраты времени и O (1) - затраты пространства

Пример:
a [] = a1, a2, ..., an
b [] = b1, b2, ..., bn
Перестановка массива в a1, b1, a2, b2, ..., an, bn

Editv1.0 : массивы a [] и b [] имеют одинаковый размер

Editv2.0 : Что делать, если вопрос расширен для перестановки в одном из заданных двух массивов, но не для создания нового массива?

Answer 1

Для простоты предположим, что массивы имеют одинаковую длину и являются int массивами.

int[] merge(int[] a, int[] b)
{
    assert (a.length == b.length);

    int[] result = new int[a.length + b.length];

    for (int i=0; i<a.length; i++)
    {
        result[i*2] = a[i];
        result[i*2+1] = b[i];
    }

    return result;
}

Answer 2

Я думаю, что это невозможно с вашими заданными ограничениями (O(n) время и O(1) пробел, то есть без дополнительного пробела) для массива или списка на основе массива. (Разумеется, при условии, что мы не можем просто создать новый объект List, делегирующий исходные.)

Если у вас есть два связанных списка, это выполнимо - если мы предположим, что сборщик мусора работает достаточно быстро, то есть удаление элемента из одного списка и добавление его в другой список не нарушает ограничение пространства.

public <X> void interleaveLists(List<X> first, List<X> second)
{
    ListIterator<X> firstIt = first.listIterator();
    ListIterator<X> secondIt = second.listIterator();
    while(secondIt.hasNext()) {
        fistIt.next();
        firstIt.add(secondIt.next());
        secondIt.remove();
    }
}

Этот метод работает для любой пары списков, но для связанных списков используется только O (n).

Для настраиваемого связанного списка, в котором мы можем изменять указатели, нам не нужно полагаться на сборщик мусора, мы просто изменили бы узлы. Здесь для односвязного списка:

public void interleaveLinkedLists(Node<X> firstList, Node<X> secondList) {
    while(secondList != null) {
        Node<X> nextFirst = firstList.next;
        Node<X> nextSecond = secondList.next;
        firstList.next = secondList;
        secondList.next = nextFirst;
        firstList = nextFirst;
        secondList = nextSecond;
    }
}

Для двусвязного списка нам также придется адаптировать предыдущие указатели.

Здесь вариант обмотки, упомянутый в первом абзаце:

public List<X> interleaveLists(final List<X> first, final List<X> second)
{
   if (first.size() != second.size())
      throw new IllegalArgumentException();
   return new AbstractList<X>() {
      public int size() {
         return 2 * first.size();
      }
      public X get(int index) {
         return index % 2 == 0 ? first.get(index / 2) : second.get(index / 2);
      }
      // if necessary, add a similar set() method.  add/remove are not sensible here.
   };
}

На самом деле это тоже O(1) во времени.

Answer 3

Я разработал небольшое решение, исходя из того, что вы говорите об использовании ArrayList (см. Мой комментарий к вопросу). Возможно, я упрощаю проблему, основываясь на некоторых ответах, но здесь все равно.

Приведенный ниже пример принимает a и b обоих типов ArrayList<Integer> и чередует их, вставляя b [0] после a [0], b [1] после a [1] и т. Д. Этот фрагмент, конечно, наивно предполагает, что a и b имеют тот же размер, что и ваш Edit v1.0. Он также не создает новый ArrayList в соответствии с вашим Edit v2.0.

//a and b are of type ArrayList<Integer>
for (int i = a.size(); i > 0; i--)
{
    a.add(i, b.get(i - 1));
}

Независимо от того, что произойдет, если вы объедините списки ArrayLists, вы получите их вдвое больше.

Answer 4

Списки не должны быть одинакового размера:

public class InterleaveTwoLists<X> {

    public List<X> interleaveLists(final List<X> first, final List<X> second) {

        return new AbstractList<X>() {
            private int minSize;
            private int combinedMinSize;
            private int size;
            private List<X>largerList;
            {{
                minSize = Math.min(first.size(), second.size());
                combinedMinSize = minSize*2;
                size = first.size() + second.size();
                largerList = first.size() > minSize ? first : second;
            }}

            public int size() {
                return size;
            }

            public X get(int index) {
                if (index < combinedMinSize) {
                    return index % 2 == 0 
                        ? first.get(index / 2) 
                        : second.get(index / 2);
                }
                else { 
                    return largerList.get(index-minSize);
                }
            }
        };
    }
}

Чтобы проверить это:

public class InterleaveTwoListsTest {

    private static final Logger log = 
        LoggerFactory.getLogger(InterleaveTwoListsTest.class);

    List<String> first = new ArrayList<String>() {
    { 
        add("one"); add("three"); add("five"); 
        add("seven"); add("eight"); add("nine");
    }};

    List<String> second = new ArrayList<String>() {
    { 
        add("two"); add("four"); add("six"); 
    }};


    private InterleaveTwoLists<String> interleaveTwoLists;

    @Before
    public void setUp() throws Exception {
        interleaveTwoLists = new InterleaveTwoLists<>();
    }

    @Test
    public void test() {
        List<String> combinedList = interleaveTwoLists.interleaveLists(first, second);
        for( int i = 0; i < first.size() + second.size(); i++) { 
            log.debug("{}: {}", i, combinedList.get(i));
        }
    }
}

Answer 5

Я считаю, что операции с модом (%) в ответе Мэтта неверны. При том же предположении (что массивы имеют одинаковую длину), я бы предложил следующее решение:

static int[] merge(final int[] a, final int[] b)
{
    final int[] result = new int[a.length * 2];

    for (int i=0; i < a.length; i++)
    {
        result[i << 1] = a[i];
        result[(i << 1) + 1] = b[i];
    }

    return result;
}

Я тестировал (очень кратко), и, похоже, он работает, но, конечно, не предпринимает попыток обработать условия ошибки, такие как нулевые аргументы или входные массивы, несовместимые по размеру.