Как эффективно добавить два целых числа, представленные двумя массивами, поместив решение в другой массив

Question

Некоторое время назад во время интервью меня попросили сложить два целых числа, представленных массивами, и поместить решение в другой массив.Часть идеи интервью была для меня, чтобы обеспечить эффективное решение.С тех пор я искал простое и эффективное решение этой проблемы, и пока не нашел ни одного.

Поэтому я хотел бы поделиться своим решением с сообществом и спросить, может ли кто-нибудь из васпомочь повысить эффективность.Этот пример выглядит как O (mn), где mn - размер самого большого массива между m или n и, где m и n - размер каждого целочисленного массива для суммирования.Таким образом, похоже, что он работает за линейное время.

public class ArrayRudiments {

    /**
     * Add two integers represented by two arrays
     * 
     * NOTE: Integer as a natural number, not as a programming language data type.
     * Thus, the integer can be as big as the array permits.
     * 
     * @param m first number as array
     * @param n second number as array
     * @return integer sum solution as array
     */
    public Integer[] sum(Integer m[], Integer n[]) {
        int carry = 0, csum = 0;
        final Vector<Integer> solution = new Vector<Integer>();

        for (int msize = m.length - 1, nsize = n.length - 1; msize >= 0 || nsize >= 0; msize--, nsize--) {

            csum = (msize < 0 ? 0 : m[msize]) + (nsize < 0 ? 0 : n[nsize]) + carry;
            carry = csum / 10;

            solution.insertElementAt(csum % 10, 0);
        }

        if (carry > 0) {
            solution.insertElementAt(carry, 0);
        }

        return solution.toArray(new Integer[] {});
    }

}

Проблема или хитрость здесь в том, что задача нелинейного времени выполняется классом Vector, вставляющим новые элементы и изменяющим размер массива решения.Таким образом, решение не работает за линейное время.Можно ли создать подобное решение без класса Vector?

Вы также можете увидеть работающую протестированную версию этого кода в https://github.com/lalounam/rudiments

Answer 1

Как сказал SSP в комментариях, вы должны создать ArrayList с начальной емкостью Math.max(m.length, n.length) + 1.Это максимальное количество цифр суммы.

int arrayCapacity = Math.max(m.length, n.length) + 1;
final List<Integer> solution = new ArrayList<>(arrayCapacity);

Затем вам нужно заполнить это 0s:

for (int i = 0 ; i < arrayCapacity ; i++) {
    solution.add(0);
}

Вот «хитрость».В основном цикле for вы не заполняете массив с самого начала, вы заполняете его с конца.Вместо insertElementAt начала, вы set элемента с любым индексом, по которому мы итерируете, плюс 1, потому что solution на единицу длиннее, чем m и n.

solution.set(Math.max(msize, nsize) + 1, csum % 10);

Это, по сути, заполнение списка «со спины».

И в конце вы изменяете размер списка следующим образом:

if (carry > 0) {
    solution.set(0, carry);
    return solution.toArray(new Integer[] {});
} else {
    return solution.subList(1, solution.size()).toArray(new Integer[] {});
}