【剑指offer】面试题66-构建乘积数组

2020-01-21
阅读量 | 字数：583字 | 预计阅读时长：2分钟

题目

给定一个数组A[0,1,…,n-1],请构建一个数组B[0,1,…,n-1],其中B中的元素B[i]=A[0]A[1]…A[i-1]*A[i+1]…*A[n-1]。不能使用除法。

1. 思路

思路1 两层循环—>O(n²)
（1）对数组B的所有元素赋初值为1，借助Arrays.fill(B, 1)即可实现，数组定义之后元素默认值为0，不初始化为1的话就白给了
（2）双重循环解决问题，仅当内层循环的下标 i 与外层循环的下标 j 相同时,才使B[i]累乘A[j]。

思路2 分部分相乘–>O(n)
思路来自《剑指offer》书籍，做题时没有考虑到这个方法，这里不再赘述思路，各位看官老爷自行查阅资料。
大体意思就是利用上、下三角矩阵的性质，分部分累乘，对B的各元素进行分步赋值，在两次时间复杂度均为O(n)的循环之后，赋值完成。

2. 代码（Java实现）

思路1

import java.util.ArrayList;
import java.util.Arrays;
public class Solution {
	public int[] multiply(int[] A) {
		int len = A.length;
		int[] B = new int[len];
		Arrays.fill(B, 1); // 数组B的元素全部赋值为1
		// def: B[i] = A[0]*A[1]* …… *A[i-1]*A[i+1]* …… *A[n];
		for (int i = 0; i < len; i++) {
			for (int j = 0; j < len; j++) {
				if (j != i) {				
					B[i] *= A[j];
				}
			}
		}
		return B;
	}
}	//O(n²)

思路2

import java.util.ArrayList;
import java.util.Arrays;
public class Solution {
	public int[] multiply(int[] A) {
		int len = A.length;
		int[] B = new int[len];
		Arrays.fill(B, 1); // 数组B的元素全部赋值为1
		// def: B[i] = A[0]*A[1]* …… *A[i-1]*A[i+1]* …… *A[n];
		
		int index = 1;
		for (index = 0; index < len; index++) {
			if(index > 0) {			//B[0] = 1
				B[index] = B[index - 1] * A[index - 1];
			}
		}
		int temp = 1;
		for (index = len - 1; index >= 0; index--) {
			if(index < len - 1) {	//B[len-1] = A[n-1]
				temp *= A[index + 1];
			}
			B[index] *= temp;	
		}
		// 输出检验
		//for (int j = 0; j < len; j++) {
		//System.out.print(B[j] + " ");
		//}
		return B;
	}
}

本想把数组类型的题全部做完，结果一下就到了66题，在《剑指offer》的书上这一小节的名字是“发散思维能力”，果然还是没能想到时间复杂度最小的解题办法，还是按部就班的按照题目顺序来做吧。

本文作者： whtli
本文链接： https://hexo.whtli.cn/archives/c0bea5f6.html
版权声明： 遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。