Объединение 2 ArrayList

 
 
 
Сообщения:1
как-то передо мной была поставлена следующая задача: даны 2 ArrayList одинаковой длины А и В. нужно написать функцию, которая вставит все элементы из В в А так, чтобы они шли по очереди, то есть (а1, b1, a2, b2 ... an, bn). Важно, чтобы сложность была наименьшей ( у меня было О (n^2) - много). помогите сделать лучше.
 
 
Сообщения:48
Не буду комментировать насчет O, но вставлять множество элементов в произвольные места ArrayList не сильно хорошая идея. Если решать в лоб, то я бы создал вспомогательный список размера n*2 и затем в цикле от 0 до n-1 добавлял последовательно элементы a[i] и b[i] в конец списка.
 
 
Сообщения:2
Можно так:

public static void main( String[] args ) {
        List<String> a = new ArrayList<String>( Arrays.asList( "a0", "a1", "a2", "a3", "a4", "a5" ) );
        List<String> b = Arrays.asList( "b0", "b1", "b2", "b3", "b4", "b5" );

        int size = a.size();
        for( int i = 0; i < size - 1; i++ ) {
            a.add( i * 2 + 1, b.get( i ) );
        }

        for( String item : a ) {
            System.out.print( item + " " );
        }
    }


результат:
a0 b0 a1 b1 a2 b2 a3 b3 a4 b4 a5
 
 
Сообщения:14
Вот с оценкой скорости (не сложности):

package fortests_001;

import java.util.ArrayList;

public class ForTests_001 {

    public static void main(String[] args) {
        final int MAX_SIZE = 100000;

        ArrayList<String> a = new ArrayList<>(MAX_SIZE);
        ArrayList<String> b = new ArrayList<>(MAX_SIZE);

        for (int i = 0; i < MAX_SIZE; i++) {
            a.add("a" + i);
            b.add("b" + i);
        }

        long ctm0, ctm1;

        // Способ 1
        ctm0 = System.currentTimeMillis();
        System.out.println("begin at " + ctm0);

        int size = a.size();
        for (int i = 0; i < size - 1; i++) {
            a.add(i * 2 + 1, b.get(i));
        }

        ctm1 = System.currentTimeMillis();
        System.out.println("end at " + ctm1 + ", time = " + (ctm1 - ctm0));

        for (String item : a) {
            System.out.print(item + " ");
        }
        System.out.println("");

        // Способ 2
        ArrayList<String> c = new ArrayList<>(MAX_SIZE);
        ArrayList<String> d = new ArrayList<>(MAX_SIZE);

        for (int i = 0; i < MAX_SIZE; i++) {
            c.add("c" + i);
            d.add("d" + i);
        }

        ctm0 = System.currentTimeMillis();
        System.out.println("begin at " + ctm0);

        Object[] ca = c.toArray(); // c array
        Object[] da = d.toArray(); // d array
        Object[] ra = new Object[ca.length + da.length]; // result array
        int cdi = 0; // Счетчик для ca и da
        for (int i = 0; i < ra.length; i += 2) {
            ra[i] = ca[cdi];
            ra[i + 1] = da[cdi];
            cdi++;
        }

        ctm1 = System.currentTimeMillis();
        System.out.println("end at " + ctm1 + ", time = " + (ctm1 - ctm0));

        for (Object item : ra) {
            System.out.print(item + " ");
        }
        System.out.println("");
    }

}


Массивы, понятное дело, гораздо быстрее, чем вставка в ArrayList.
Вопрос - а как оценить сложность Способа 2?
 
 
Сообщения:48
Max_Sys:
Массивы, понятное дело, гораздо быстрее, чем вставка в ArrayList.

Второй способ можете смело заменить моим предложением о вспомогательном списке. Скорость будет та же самая, только избавитесь от представления данных как массивов. Просто надо иметь в виду что, когда пользуешься array list'ом, то работаешь с оберткой для массива. Можете посмотреть, чем отличаются методы add(idx, e) и add(e) у ArrayList, будет полезно.
Относительно O могу предложить такой вариант: оцениваете количество необходимых действий для получения результата, умножаете на количество итераций и получаете алгоритмическую сложность. Она, правда, не учитывает затраты памяти на алгоритм, так что в голом варианте знание алгоритмической сложности довольно бесполезно.
 
Модераторы:Нет
Сейчас эту тему просматривают:Нет