LeetCode 238 Product of Array Except Self

henry14 发布于2019-08-14 17:43 / 544人阅读

Given an array of n integers where n > 1, nums, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].
Solve it without division and in O(n).

For example, given [1,2,3,4], return [24,12,8,6].

Follow up:
Could you solve it with constant space complexity? (Note: The output array does not count as extra space for the purpose of space complexity analysis.)

有三种情况：
数组元素不含0，像[1,2,3,4], return [24,12,8,6]
数组元素有1个0，[1,0,3,4], return [0,12,0,0]，是0的那个位置是其他元素的乘积
数组元素有2个或者2个以上0，[1,0,0,4]则返回[0,0,0,0],返回全部是0.

public class ProductArrayExceptSelf {
    public int[] solution(int[] nums) {
        int zeroCount = 0;
        for (int n : nums)
            if (n == 0)
                zeroCount++;
        // 有两个或者两个以上的元素是0，那么数组设为全零返回
        if (zeroCount > 1) {
            for (int i = 0; i < nums.length; i++)
                nums[i] = 0;
        } else if (zeroCount == 0) {
            // 如果没有0，则计算所有的乘积
            int product = 1;
            for (int n : nums)
                product *= n;
            // 每个数组元素置为product / 该位置值即可
            for (int i = 0; i < nums.length; i++)
                nums[i] = product / nums[i];
        } else {
            // 如果元素中有1个0
            int product = 1;
            // 跳过那个元素，计算所有的乘积
            for (int n : nums)
                if (n != 0)
                    product *= n;
            // 元素为0的位置置为product，其他置为0
            for (int i = 0; i < nums.length; i++)
                if (nums[i] == 0)
                    nums[i] = product;
                else
                    nums[i] = 0;
        }
        return nums;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(new ProductArrayExceptSelf().solution(new int[] { 1, 0, 3, 0 })));
    }
}

补上one pass 且不用除法, o(n)解法。
使用左右指针，一遍遍历即可

    public int[] solution2(int[] nums) {
        int[] result = new int[nums.length];
        Arrays.fill(result, 1);
        int left = 1, right = 1;
        int len = nums.length;
        for (int i = 0; i < len; i++) {
            result[i] *= left;
            result[len - 1 - i] *= right;
            left *= nums[i];
            right *= nums[len - i - 1];
            //System.out.println(Arrays.toString(result));
        }
        return result;
    }

海外云主机服务器托管 Except LeetCode Product LeetCode_String

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/66760.html

【Python】LeetCode 238. Product of Array Except Self

摘要：题目描述题目解析简单来说就是对于数组中每一项，求其他项之积。算一遍全部元素的积再分别除以每一项要仔细考虑元素为零的情况。没有零直接除下去。一个零零的位置对应值为其他元素之积，其他位置为零。两个以上的零全部都是零。题目描述 Given an array of n integers where n > 1, nums, return an array output such that o...

kaka 2019-07-31 12:22 评论0 收藏0
[LeetCode] 238. Product of Array Except Self

Problem Given an array of n integers where n > 1, nums, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i]. Solve it without division and in ...

Loong_T 2019-08-14 14:32 评论0 收藏0
238. Product of Array Except Self

问题：Given an array of n integers where n > 1, nums, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i]. Solve it without division and in O(n)....

刘永祥 2019-08-14 14:18 评论0 收藏0
[LeetCode] Product of Array Except Self

Problem Given an array of n integers where n > 1, nums, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i]. Solve it without division and in ...

golden_hamster 2019-08-16 11:14 评论0 收藏0
[Leetcode] Product of Array Except Self 自身以外的数组乘积

摘要：动态规划复杂度时间空间思路分析出自身以外数组乘积的性质，它实际上是自己左边左右数的乘积，乘上自己右边所有数的乘积。所以我们可以用一个数组来表示第个数字前面数的乘积，这样。同理，我们可以反向遍历一遍生成另一个数组。 Product of Array Except Self Given an array of n integers where n > 1, nums, return an...

rockswang 2019-08-14 12:34 评论0 收藏0