By

文章目录
  1. 1. 题目
  2. 2. 解答
  3. 3. 代码
  4. 4. 参考

题目

给定一个数组a[N]，我们希望构造数组b [N]，其中b[j]=a[0]*a[1]…a[N-1] / a[j]，在构造过程中，不允许使用除法：要求O（1）空间复杂度和O（n）的时间复杂度；除遍历计数器与a[N] b[N]外，不可使用新的变量（包括栈临时变量、堆空间和全局静态变量等）

解答

不能使用除法，那就不能直接全部做乘法再做除法。
b[j]=a[0]*a[1]…a[N-1] / a[j]，其实就是a中除去第j个数其他数相乘。
既然不能使用除法，就只能将整个式子分成两部分：a[0]*a[1]*...*a[j-1] 和 a[j+1]*a[j+2]*...*a[N-1]

  1. 首先构造第一部分
    令b[0] = 1 , b[j] = b[j-1]*a[j-1]
    b[1] = a[0]
    b[2] = a[0]*a[1]
    …
    b[j] = a[0]*a[1]*…*a[j-1]
    …
    b[n-1] = a[0]*a[1]*…*a[n-2]

  2. 然后开始构造第二部分
    因为初始都是从1开始构造，所以这次我们需要从后往后前构造。
    令b[0] = 1 , b[j] = b[0]*b[j] ，每次前进重新计算b[0]的值，作为临时变量 : b[0]= b[0]*a[j]

    b[n-1] = a[0]*a[1]*…*a[n-2]* 1 , b[0] = a[n-1]
    b[n-2] = a[0]*a[1]*…*a[n-3]* a[n-1] , b[0] = a[n-1]*a[n-2]
    b[n-3] = a[0]*a[1]*…*a[n-4]*a[n-2]* a[n-1] , b[0] = a[n-1]*a[n-2]*a[n-3]
    …
    b[j] = a[0]*a[1]*…*a[j-1].*a[j+1]* a[j+2]*..*a[n-2]* a[n-1] , b[0] = a[n-1]*a[n-2]*..*a[j]
    …
    b[1] = a[0]*a[2]*…*a[n-3]*a[n-2]* a[n-1], b[0] = a[n-1]*a[n-2]*..*a[1]

    此部分，每当计算b[j]时，b[0] = a[n-1]*a[n-2]*...a[j] ,正好是下一次需要计算的右边部分。
    此时，所有的b[j] 都满足 b[j]=a[0]*a[1]…a[N-1] / a[j]

    代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    public int[] translate(int a[])
    {
        int len = a.length;
        int[] b = new b[len];
        b[0] = 1;
        for (int j = 1; j <= len-1; j++)
        {
            b[j] = b[j-1]*a[j-1];
        }

        for (int j = len-1; j >= 1; j--)
        {
            b[j] *= b[0];
            b[0] *= a[j];
        }
        return b;
    }

参考

[1]: 给定数组a[N]构造数组b [N]——腾讯笔试

文章目录
  1. 1. 题目
  2. 2. 解答
  3. 3. 代码
  4. 4. 参考