ITeye博客

Product of Array Except Self

KickCode · 2016-02-24 02:43 · Leetcode · 编程语言 · Markdown

Given an array of n integers where n > 1, nums, return an array output such that output* is equal to the product of all the elements of nums except nums*.

Solve it without division and in O(n).

For example, given , return .

我们创建一个长度和原数组num长度一样的数组result,先从左边开始,让result = 1; result = 1 * num, result = num * num, result = num * num ...num。然后从右边开始,让result = result * 1; result = num * result; result = num * num .... num * result。这样遍历两遍数组就可以得到结果,代码如下:


public class Solution {
    public int[] productExceptSelf(int[] nums) {
        int[] result = new int[nums.length];
        int left = 1;
        result[0] = 1;
        for(int i = 1; i < nums.length; i++) {
            result[i] = left * nums[i - 1];
            left *= nums[i - 1];
        }
        int right = 1;
        for(int j = nums.length - 1; j >= 0; j--) {
            result[j] *= right;
            right *= nums[j];
        }
        return result;
    }
}

评论(0)

暂无评论。

评论功能维护中,当前仅展示历史评论。