问题描述

用数组的形式来计算两个整数的乘法。例如193707721 X -761838257287 = -147573952589676412927，则输入两个数组(1,9,3,7,0,7,7,2,1)和(-7,6,1,8,3,8,2,5,7,2,8,7)，返回数组(-1,4,7,5,7,3,9,5,2,5,8,9,6,7,6,4,1,2,9,2,7)。

思路阐述

首先考虑两种极端情况：以9x99和1x10而言，前者结果是3位数，后者结果是2位数，也就是说n位数与m位数相乘，结果最多也就是n+m位，可能比这个数小。
这意味着，假设输入的是两个数组A和B，大小分别为n和m，结果数组可以预先开辟为n+m位全0数组，最后移去前面可能存在的0.
然后就是符号，这个很好解决，先提取出来，最后再加上去，这样只要考虑两个正数相乘的情况。
之后考虑乘法的核心算法：如何进行乘法？
乘法最本质的定义，axb就是b个a相加。当然这里并没有说不能使用普通乘法，只是数字太大会溢出，不过如果能确保不溢出，直接使用乘法运算无疑是最简单的。
也就是说，以123x45为例，分别需要计算100x40+100x5+20x40+20x5+3x40+3x5，或者说A和B的每个数分别轮流相乘。
单独来看，A[i]xB[j]，因为1位x1位结果只能是1位或者2位，因此A[i]xB[j]的结果将位于结果的i+j与i+j+1位。这里仍以123x45为例，A[0]=3，B[1]=4,真实结果是3x40=120，除去0以外对应结果的1和2序号。
不过这里产生一个问题：进位如何处理？可以每次清算，也可以在最后再一次清算。
代码：

public static List <Integer> multiply (List <Integer> num1 , List <Integer > num2) {
    final int sign = numl. get (0) < 0 ^  A num2.get(0) < 0 ? -1 : 1;
    num1 . set (0 , Math . abs (numl .get(0)));
    num2 . set (0 , Math . abs (num2 .get(0)));

    List<Integer > result = new ArrayList <>(Collections . nCopies (numl . size () + num2.size(), 0));
    for (int i = num1.size() - 1; i >= 0; --i) {
        for (int j = num2.size() - 1; j >= 0 ; --j) {
            result .set (i + j + 1 , result.get(i + j + 1) + num1.get(i) * num2 . get ( j) ) ;
            result.set(i + j, result.get(i + j) + result.get(i + j + 1) / 10);
            result.set(i + j + 1, result.get(i + j + 1) % 10);
        }
    }
    // Remove the leading zeroes.
    int first_not_zero = 0;
    while (first_not_zero < result . size () && result.get (first_not_zero) == 0) {
        ++first_not_zero ;
    }
    result = result. subList (first_not_zero , result .size () ) ;
    if (result. isEmpty () ) {
        return Arrays. asList (0) ;
    }
    result .set (0 , result . get (0) * sign);
    return result;
}

时间复杂度O(mn)。