不使用除法,线性复杂度给数组赋值

一个长度为n的数组a[0],a[1],...,a[n-1]。现在更新数组的名个元素,即a[0]变为a[1]到a[n-1]的积a[1]变为a[0]和a[2]到a[n-1]的积,...,a[n-1]为a[0]到a[n-2]的积。

程序要求:

要求具有线性复杂度。

不能使用除法运算符

private void transfer(int[] a) {

       int n = a.length;

       int[] b = new int[n];

       int[] c = new int[n];

      

       b[0] = 1;

       c[n-1] = 1;

      

       for(int i=1; i<n; i++) {

           b[i] = b[i-1]*a[i-1];

           c[n-i-1] = c[n-i]*a[n-i];

       }

      

       for(int i=0; i<n; i++) {

           a[i] = b[i]*c[i];

       }

    }


原文地址:https://www.cnblogs.com/allenzhaox/p/3201793.html