Interview Return Products of All Other Elements in Array

这是一道面试亚马逊时的题目，要求Time O(n). 我刚开始想的是算出所有的数的总product，再去除以对应位置的元素，但这种做法的问题是若该位置为0，就会报错。

到网上搜了下，才知道，原来有这种做法。

e.g. arr = {0,1,2,3}，生成两个array： upArr = {1,arr[0],
arr[0]*arr[1],arr[0]*arr[1]*arr[2]}

downArr = {arr[0]*arr[1]*arr[2],arr[1]*arr[2],
arr[2],1}

最后的结果res就是upArr 和 downArr 对应的位置相乘即可。Time O(n).

Note: 1.System.out.println arr 时可用 Arrays.toString(arr).

AC Java:

import java.util.*;

public class productOthers{

	public static void main(String [] args){

		int[] myArr = {0,1,2,3,4};

		int[] myArr2 = {2,4,3,5};

		int[] myArr3 = null;

		System.out.println(Arrays.toString(productOthers(myArr)));

		System.out.println(Arrays.toString(productOthers(myArr2)));

		System.out.println(Arrays.toString(productOthers(myArr3)));

	}

	private static int [] productOthers(int [] arr){

		if(arr == null || arr.length == 0)

			return null;

		int[] upArr = new int[arr.length];

		int[] downArr = new int[arr.length];

		int[] res = new int[arr.length];

		upArr[0] = 1;

		int mul1 = arr[0];

		for(int i = 1; i < upArr.length; i++){

			upArr[i] = mul1;

			mul1*=arr[i];

		}

		// System.out.println(Arrays.toString(upArr));

		downArr[downArr.length-1] = 1;

		mul1 = arr[arr.length-1];

		for(int i = downArr.length-2;i>=0;i--){

			downArr[i] = mul1;

			mul1*=arr[i];

		}

		// System.out.println(Arrays.toString(downArr));

		for(int i = 0; i<arr.length; i++){

			res[i] = upArr[i]*downArr[i];

		}

		return res;

	}

}