Product of Array Except Self-K6K4.com

原题： https://leetcode.com/problems/product-of-array-except-self/description/

题意： 给定长度为n的整数数组nums，其中n > 1，返回输出数组output，满足output[i]等于除nums[i]之外其余各数的乘积。不使用除法，在O(n)时间复杂度内完成此题目。

进一步思考：你可以在常数空间复杂度内完成题目吗？（注意：输出数组不算在空间复杂度分析中）

例子：

给定 [1,2,3,4]
返回 [24,12,8,6]

标签： nums、product、各数、复杂度、array、面试

猜你感兴趣的圈子：

LeetCode交流圈

Bingo

2017-08-18 17:42:31 1楼#1层

Python：

class Solution:
    # @param {integer[]} nums
    # @return {integer[]}
    def productExceptSelf(self, nums):
        size = len(nums)
        output = [1] * size
        left = 1
        for x in range(size - 1):
            left *= nums[x]
            output[x + 1] *= left
        right = 1
        for x in range(size - 1, 0, -1):
            right *= nums[x]
            output[x - 1] *= right
        return output

Bingo

2017-08-18 17:42:58 2楼#1层

C++解法一：

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> fwd(n, 1), bwd(n, 1), res(n);
        for (int i = 0; i < n - 1; ++i) {
            fwd[i + 1] = fwd[i] * nums[i];
        }
        for (int i = n - 1; i > 0; --i) {
            bwd[i - 1] = bwd[i] * nums[i];
        }
        for (int i = 0; i < n; ++i) {
            res[i] = fwd[i] * bwd[i];
        }
        return res;
    }
};

Bingo

2017-08-18 17:43:27 3楼#1层

C++解法二：

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        vector<int> res(nums.size(), 1);
        for (int i = 1; i < nums.size(); ++i) {
            res[i] = res[i - 1] * nums[i - 1];
        }
        int right = 1;
        for (int i = nums.size() - 1; i >= 0; --i) {
            res[i] *= right;
            right *= nums[i];
        }
        return res;
    }
};

Bingo

2017-08-18 17:43:46 4楼#1层

Java解法一：

public class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] res = new int[n];
        int[] fwd = new int[n], bwd = new int[n];
        fwd[0] = 1; bwd[n - 1] = 1;
        for (int i = 1; i < n; ++i) {
            fwd[i] = fwd[i - 1] * nums[i - 1];
        }
        for (int i = n - 2; i >= 0; --i) {
            bwd[i] = bwd[i + 1] * nums[i + 1];
        }
        for (int i = 0; i < n; ++i) {
            res[i] = fwd[i] * bwd[i];
        }
        return res;
    }
}

Bingo

2017-08-18 17:44:00 5楼#1层

Java解法二：

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

取消

回复

推荐圈子

LeetCode交流圈