[LeetCode 笔记] 238. Product of Array Except Self

前言

　　这题有点类似 Prefix Sums 的概念，目标是找到阵列中元素自己以外的所有元素的乘绩，放在一个新的阵列里，虽然有三个迴圈是 O(3n) 的时间複杂度，但常数项通常会被省略，因此该演算法可达 O(n) 的时间複杂度，这里有 JAVA 和 Python 的写法。

题目

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].
The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.
You must write an algorithm that runs in O(n) time and without using the division operation.

给定一个整数阵列 nums，回传一个阵列 answer ，其中 answer[i] 等于所有元素的乘积，除了 nums[i]
保证 nums 阵列中任何的前后缀都适合 32-bit 的整数
你必须写出一个时间複杂度为 O(n) 的算法且不能使用除法

题目连结：https://leetcode.com/problems/product-of-array-except-self/

题目限制

2 <= nums.length <= 105
30 <= nums[i] <= 30

The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

範例

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

nums [0] ⇒ 把 2、3、4 都乘起来
nums [1] ⇒ 把 1、3、4 都乘起来
(以此类推)
把全部乘完的元素都放在 answer 里

Input: nums = [-1,1,0,-3,3]Output: [0,0,9,0,0]

nums [0] ⇒ 把 1、0、-3、3 都乘起来
nums [1] ⇒ 把 -1、0、-3、3 都乘起来
(以此类推)
把全部乘完的元素都放在 answer 里

思路&笔记

简而言之我们要把除了 nums[i] 以外的元素乘起来，并且对每一个 i 做一样的事情然后每个索引之前之后的元素都要相乘，就是 自己前面的乘积 * 自己后面的乘积

JAVA 实现

class Solution {    public int[] productExceptSelf(int[] nums) {                int left[] = new int[nums.length]; // 前缀乘积        int right[] = new int[nums.length]; // 后缀乘积        int answer[] = new int[nums.length];        left[0] = 1; // 第一个元素设为 1        right[nums.length-1] = 1; // 阵列最后一个元素设为 1        for (int i = 1; i < nums.length; i++){            left[i] = nums[i - 1] * left[i - 1]; // left = [1, 1, 2, 6]        };        // 计数器 i 从阵列后面递减回来        for (int i = nums.length-2; i >= 0; i--){            right[i] = nums[i + 1] * right[i + 1]; // right = [24, 12, 4, 1]        };        // 把两个阵列的乘积相乘        for (int i = 0; i < nums.length; i++){            answer[i] = left[i] * right[i];        };        return answer;     }}

Python 实现

使用了和 Java 一样的逻辑执行，换成 Python 的写法。

class Solution:    def productExceptSelf(self, nums: List[int]) -> List[int]:        left, right, answer = [0] * len(nums), [0] * len(nums), [0] * len(nums)        left[0] = 1 # 第一个元素设为 1        right[len(nums)-1] = 1 # 阵列最后一个元素设为 1        for i in range(1, len(nums)):            left[i] = nums[i-1] * left[i-1]        # 计数器 i 从阵列后面递减回来        for i in range(len(nums)-2, -1, -1):            right[i] = nums[i+1] * right[i+1]                # 把两个阵列的乘积相乘        for i in range(len(nums)):            answer[i] = left[i] * right[i]                return answer

成绩

Blog
https://chris81051.github.io/2023/10/28/LeetCode-238-Product-of-Array-Except-Self-Java-Python/
有分享技术文章、科技新闻、日常生活，欢迎一起讨论