238. Product of Array Except Self

栏目: Java · 发布时间: 5年前

内容简介:Given an array nums of n integers where n > 1, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].Example:Note: Please solve it without division and in O(n).

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

Example:

Input:  [1,2,3,4]
Output: [24,12,8,6]

Note: Please solve it without division and in O(n).

Follow up:

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

难度: medium

题目:给定一整数组其长度大于1, 返回输出数组其元素由除当前输入元素外所有元素的乘积组成。

思路:先用输出数组从右向左计算累积元素的乘积,然后从左向左计算nums[i] = product(0, i-1) * result(i + 1)

Runtime: 1 ms, faster than 100.00% of Java online submissions for Product of Array Except Self.

Memory Usage: 40.8 MB, less than 84.97% of Java online submissions for Product of Array Except Self.

class Solution {
    public int[] productExceptSelf(int[] nums) {
        if (null == nums || nums.length < 2) {
            return new int[] {1};
        }
        int n = nums.length;
        int[] result = new int[n];
        int product = 1;
        for (int i = n - 1; i >= 0; i--) {
            result[i] = product * nums[i];
            product = result[i];
        }
        
        result[0] = result[1];
        product = nums[0];
        for (int i = 1; i < n - 1; i++) {
            result[i] = product * result[i + 1];
            product *= nums[i];
        }
        result[n - 1] = product;
        
        return result;
    }
}

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

Practical JavaScript, DOM Scripting and Ajax Projects

Practical JavaScript, DOM Scripting and Ajax Projects

Frank Zammetti / Apress / April 16, 2007 / $44.99

http://www.amazon.com/exec/obidos/tg/detail/-/1590598164/ Book Description Practical JavaScript, DOM, and Ajax Projects is ideal for web developers already experienced in JavaScript who want to ......一起来看看 《Practical JavaScript, DOM Scripting and Ajax Projects》 这本书的介绍吧!

CSS 压缩/解压工具
CSS 压缩/解压工具

在线压缩/解压 CSS 代码

html转js在线工具
html转js在线工具

html转js在线工具

HEX HSV 转换工具
HEX HSV 转换工具

HEX HSV 互换工具