L1-数组剔除元素后的乘积

Posted on | In |

描述
给定一个整数数组A。

定义 B[i] = A[0] … A[i-1] A[i+1] … * A[n-1]， 计算B的时候请不要使用除法。

样例
给出A=[1, 2, 3]，返回 B为[6, 3, 2]

法一

java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Solution {
	/*
	 * @param nums: Given an integers array A
	 * 
	 * @return: A long long array B and B[i]= A[0] * ... * A[i-1] * A[i+1] * ...
	 * * A[n-1]
	 */
	public List<Long> productExcludeItself(List<Integer> nums) {
		// write your code here
		List<Long> newNums = new ArrayList();
		for (int i = 0; i < nums.size(); i++) {
			long sum = 1;
			for (int j = 0; j < nums.size(); j++) {
				if (j == i)
					continue;
				else
					sum *= nums.get(j);

			}
			newNums.add(sum);
		}
		return newNums;
	}
}

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:  
    """ 
    @param: nums: Given an integers array A 
    @return: A long long array B and B[i]= A[0] * ... * A[i-1] * A[i+1] * ... * A[n-1] 
    """  
    def productExcludeItself(self, nums):  
        # write your code here  
        result = []  
        for i in range(len(nums)):  
            temp = 1  
            for j in range(len(nums)):  
                if j != i:  
                    temp *= nums[j]  
            result.append(temp)  
        return result

法二

java
前后遍历 把左右的积都算一下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Solution {
    /*
     * @param nums: Given an integers array A
     * @return: A long long array B and B[i]= A[0] * ... * A[i-1] * A[i+1] * ... * A[n-1]
     */
	public List<Long> productExcludeItself(List<Integer> nums) {
		// write your code here
		int n=nums.size();
		List<Long> newNums = new ArrayList();
		Long[] left=new Long[n];
		Long[] right=new Long[n];
		for(int i=0;i<n;i++)
			{left[i]=(long) 1;
			right[i]=(long) 1;
			}
		for(int i=1;i<n;i++)
			left[i]=left[i-1]*nums.get(i-1);
		for(int i=n-2;i>=0;i--)
			right[i]=right[i+1]*nums.get(i+1);
		for(int i=0;i<n;i++)
			newNums.add(left[i]*right[i]);
		return newNums;
	}
}