問題描述

用數(shù)組的形式來計(jì)算兩個(gè)整數(shù)的乘法。例如193707721 X -761838257287 = -147573952589676412927，則輸入兩個(gè)數(shù)組(1,9,3,7,0,7,7,2,1)和(-7,6,1,8,3,8,2,5,7,2,8,7)，返回?cái)?shù)組(-1,4,7,5,7,3,9,5,2,5,8,9,6,7,6,4,1,2,9,2,7)。

思路闡述

首先考慮兩種極端情況：以9x99和1x10而言，前者結(jié)果是3位數(shù)，后者結(jié)果是2位數(shù)，也就是說n位數(shù)與m位數(shù)相乘，結(jié)果最多也就是n+m位，可能比這個(gè)數(shù)小。
這意味著，假設(shè)輸入的是兩個(gè)數(shù)組A和B，大小分別為n和m，結(jié)果數(shù)組可以預(yù)先開辟為n+m位全0數(shù)組，最后移去前面可能存在的0.
然后就是符號(hào)，這個(gè)很好解決，先提取出來，最后再加上去，這樣只要考慮兩個(gè)正數(shù)相乘的情況。
之后考慮乘法的核心算法：如何進(jìn)行乘法？
乘法最本質(zhì)的定義，axb就是b個(gè)a相加。當(dāng)然這里并沒有說不能使用普通乘法，只是數(shù)字太大會(huì)溢出，不過如果能確保不溢出，直接使用乘法運(yùn)算無疑是最簡(jiǎn)單的。
也就是說，以123x45為例，分別需要計(jì)算100x40+100x5+20x40+20x5+3x40+3x5，或者說A和B的每個(gè)數(shù)分別輪流相乘。
單獨(dú)來看，A[i]xB[j]，因?yàn)?位x1位結(jié)果只能是1位或者2位，因此A[i]xB[j]的結(jié)果將位于結(jié)果的i+j與i+j+1位。這里仍以123x45為例，A[0]=3，B[1]=4,真實(shí)結(jié)果是3x40=120，除去0以外對(duì)應(yīng)結(jié)果的1和2序號(hào)。
不過這里產(chǎn)生一個(gè)問題：進(jìn)位如何處理？可以每次清算，也可以在最后再一次清算。
代碼：

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;
}

時(shí)間復(fù)雜度O(mn)。