LeetCode 238. Product of Array Except Self

简介: 给定长度为 n 的整数数组 nums,其中 n > 1,返回输出数组 output ,其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。

v2-a3264b2e9b007c24daa0b69d76ac2c32_1440w.jpg

Description



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.)


描述



给定长度为 n 的整数数组 nums,其中 n > 1,返回输出数组 output ,其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。


示例:


输入: [1,2,3,4]

输出: [24,12,8,6]

说明: 请不要使用除法,且在 O(n) 时间复杂度内完成此题。


进阶:

你可以在常数空间复杂度内完成这个题目吗?( 出于对空间复杂度分析的目的,输出数组不被视为额外空间。)


思路



  • 声明一个结果数组res,用于返回结果.
  • 我们首先正向遍历数组,获取当前位置左边的数的所有乘积,即


v2-adacf910fc8d7bcbf1bf8465dd781dcc_720w.jpg


也就是


v2-6f4082c0a709b679f3add924b7a5b11a_720w.jpg


  • 我们声明一个辅助变量_product用于记录当前位置右边的所有数字的乘积,于是根据定义,位置i的值为(i左边所有数的乘积)与(i右边所有数的乘积)的乘积.
  • 所以res[i]= res[i](i左边所有数的乘积)*_product(i右边所有数的乘积),然后我们更新_product *= nums[i].
# -*- coding: utf-8 -*-
# @Author:             何睿
# @Create Date:        2019-02-02 08:52:08
# @Last Modified by:   何睿
# @Last Modified time: 2019-02-02 09:01:08
class Solution:
    def productExceptSelf(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        # 声明结果数组,第一个位置(索引0)一定要初始化为1
        res = [1 for _ in range(len(nums))]
        # 辅助变量
        _product = nums[-1]
        # 正向遍历,获取当前位置左边的所有数字乘积的值
        for i in range(1, len(nums)):
            res[i] = res[i - 1] * nums[i - 1]
        # 反向遍历,_product表示当前位置右边的数所有乘积的值
        for i in range(len(nums) - 2, -1, -1):
            # 当前位置的值等与当前位置左右两边所有数的乘积
            res[i] = _product * res[i]
            _product *= nums[i]
        # 返回结果
        return res

源代码文件在这里.


目录
相关文章
Leetcode Find Minimum in Rotated Sorted Array 题解
对一个有序数组翻转, 就是随机取前K个数,移动到数组的后面,然后让你找出最小的那个数,注意,K有可能是0,也就是没有翻转。
272 0
|
算法 Python
LeetCode 410. Split Array Largest Sum
给定一个非负整数数组和一个整数 m,你需要将这个数组分成 m 个非空的连续子数组。设计一个算法使得这 m 个子数组各自和的最大值最小。
367 0
LeetCode 410. Split Array Largest Sum
|
算法
LeetCode 330. Patching Array
给定一个已排序的正整数数组 nums,和一个正整数 n 。从 [1, n] 区间内选取任意个数字补充到 nums 中,使得 [1, n] 区间内的任何数字都可以用 nums 中某几个数字的和来表示。请输出满足上述要求的最少需要补充的数字个数。
326 0
LeetCode 330. Patching Array
LeetCode contest 200 5476. 找出数组游戏的赢家 Find the Winner of an Array Game
LeetCode contest 200 5476. 找出数组游戏的赢家 Find the Winner of an Array Game
|
算法 Python
LeetCode 108. 将有序数组转换为二叉搜索树 Convert Sorted Array to Binary Search Tree
LeetCode 108. 将有序数组转换为二叉搜索树 Convert Sorted Array to Binary Search Tree
|
算法 测试技术
LeetCode 88. 合并两个有序数组 Merge Sorted Array
LeetCode 88. 合并两个有序数组 Merge Sorted Array
|
人工智能 索引
LeetCode 1013. 将数组分成和相等的三个部分 Partition Array Into Three Parts With Equal Sum
LeetCode 1013. 将数组分成和相等的三个部分 Partition Array Into Three Parts With Equal Sum
LeetCode 189. 旋转数组 Rotate Array
LeetCode 189. 旋转数组 Rotate Array
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
643 6
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
666 2

热门文章

最新文章

  • 1
    PHP 数组查找:为什么 `isset()` 比 `in_array()` 快得多?
    435
  • 2
    Java 中数组Array和列表List的转换
    1237
  • 3
    JavaScript中通过array.map()实现数据转换、创建派生数组、异步数据流处理、复杂API请求、DOM操作、搜索和过滤等,array.map()的使用详解(附实际应用代码)
    910
  • 4
    通过array.reduce()实现数据汇总、条件筛选和映射、对象属性的扁平化、转换数据格式、聚合统计、处理树结构数据和性能优化,reduce()的使用详解(附实际应用代码)
    1703
  • 5
    通过array.some()实现权限检查、表单验证、库存管理、内容审查和数据处理;js数组元素检查的方法,some()的使用详解,array.some与array.every的区别(附实际应用代码)
    918
  • 6
    通过array.every()实现数据验证、权限检查和一致性检查;js数组元素检查的方法,every()的使用详解,array.some与array.every的区别(附实际应用代码)
    639
  • 7
    多维数组操作,不要再用遍历循环foreach了!来试试数组展平的小妙招!array.flat()用法与array.flatMap() 用法及二者差异详解
    478
  • 8
    别再用双层遍历循环来做新旧数组对比,寻找新增元素了!使用array.includes和Set来提升代码可读性
    450
  • 9
    Array.forEach实战详解:简化循环与增强代码可读性;Array.forEach怎么用;面对大量数据时怎么提高Array.forEach的性能
    330
  • 10
    深入理解 JavaScript 中的 Array.find() 方法:原理、性能优势与实用案例详解
    988