当前位置:   article > 正文

LeetCode 238. Product of Array Except Self 解题报告_java leetcode 238

java leetcode 238

LeetCode 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].


示例

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


限制条件

  • Solve it without division and in O(n).
  • 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.)

解题思路

我的思路:

首先试了一下用两个for循环嵌套求解,时间复杂度是O(n2),所以理所当然地没过。好吧,终究没有想出什么头绪来,只能可耻地看了Discuss外加必应了。查到的解法都相似,下面给出正确的解法。(其实这段就是废话。。。)

参考思路:

数组a包含4个元素。
构建如下两个数组front和back:

数组名
front1a[0]a[0] * a[1]a[0] * a[1] * a[2]
backa[3] * a[2] * a[1]a[3] * a[2]a[3]1

通过将这两个数组的元素对应相乘,我们就能得到题目要求的,除了自身以外所有数组元素的乘积。

第一个数组front的构建方式是front[0]设置为1,从第2位开始,使用一个变量temProduct存储从a[0]到当前a[i -1]的乘积,每次都把这个乘积赋给front[i]。
第二个数组back的构建方式类似,不过从数组a最后一个元素开始,设置back[n - 1]为1(n 为数组a的大小),从倒数第二位开始,使用一个变量temProduct存储从a[n - 1]到当前a[i + 1]的乘积,每次都把这个乘积赋给back[i]。
最后将这两个数组元素对应相乘即得到结果。

为了节省空间,可以直接使用要返回的数组product作为那两个数组:首先是作为front数组,操作过程一样,然后作为back数组时是直接在当前元素上乘以temProduct。见参考代码1。

为了构建这两个数组需要两个for循环,它们的区别是遍历数组a的顺序不同,所以还可以合并,只用一个for循环同时进行对product[i] 和 product[n - i -1]的操作。见参考代码2。


代码

参考代码1
class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        vector<int> product(nums.size(), 1);
        int temProduct = 1;

        for (int i = 0; i < nums.size(); i++) {
            product[i] = temProduct;
            temProduct *= nums[i];
        }

        for (int i = nums.size() - 1, temProduct = 1; i >= 0; i--) {
            product[i] *= temProduct;
            temProduct *= nums[i];
        }

        return product;
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
参考代码2
class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        int frontProduct = 1;
        int backProduct = 1;
        vector<int> product(n, 1);

        for (int i = 0; i < n; i++) {
            product[i] *= frontProduct;
            frontProduct *= nums[i];
            product[n - i - 1] *= backProduct;
            backProduct *= nums[n - i - 1];
        }

        return product;
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18

总结

今天蛮失败的,自己没有想出这道题的解法,还是靠看其他人的解法才知道应该怎么做,不得不说,这道题的解法真的是很巧妙,让我大开眼界。还处于菜鸟的我真的要加油,多刷题,多见识见识了。
我填坑,我快乐,继续加油!

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/Li_阴宅/article/detail/818385
推荐阅读
相关标签
  

闽ICP备14008679号