资讯专栏INFORMATION COLUMN

LeetCode 238 Product of Array Except Self

henry14 / 603人阅读

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;
    }

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

转载请注明本文地址: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 评论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 评论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)....

    刘永祥 评论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 评论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 评论0 收藏0

发表评论

0条评论

henry14

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<