【leetcode】238. 除自身以外数组的乘积

题目内容

思路分析

按理说比较容易想到的一个O(n)的解是把所有数乘起来，然后除以nums[i]。然而该方法遇到0会失效，且题目不允许用除法。最重要的是我连这种方法都想不到...

方法一：左右乘积列表

可以维护两个乘积列表left_multi和right_multi，该列表的第i个值代表着nums中的第i个数（注意，非nums[i]）及其左边所有数字的乘积，left_multi第0个值为1，right_multi的最后一个值为1，然后依次遍历数组nums，将left_multi[左]和right_multi[右]添加进结果数组中。将第0个值/最后一个值设为1主要是为了遍历nums的第一个数和最后一个数时方便。

方法二：左右乘积列表plus

题目中有一个进阶要求是使用O(1)的空间复杂度，由于空间复杂度是不计算答案数组所占空间的，因此考虑在答案数组中放入左右乘积列表。具体做法如下：

创建一个大小为n = nums.size()的答案数组answer
初始化左乘积列表，answer[i]代表第i个元素及其所有左侧元素的乘积。需要注意的是这里只开拓了大小为n的数组，因此没有像方法1一样将1放入数组的第一个位置。
设置变量right_multi=1，倒序遍历nums数组，一边计算答案answer[i]=answer[i-1]*right_multi，一边更新right_multi，在数组的第一个位置进行特殊处理：answer[0]=1*right_multi

代码

#include <vector>
#include <math.h>
#include <limits.h>

using namespace std;

// 左右乘积列表
// 时间复杂度O(n)
// 空间复杂度O(n)
class Solution1 {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
       int n = nums.size();

       // 左右乘积列表初始化
       vector<int> left_multi(n+1, 1), right_multi(n+1, 1), result;
       for (int i = 0; i < n; ++i) {
          left_multi[i + 1] = left_multi[i] * nums[i];
       }
       for (int i = n - 1; i >= 0; --i) {
          right_multi[i] = right_multi[i + 1] * nums[i];
       }

       for (int i = 0; i < n; ++i) {
          result.push_back(left_multi[i] * right_multi[i + 1]);
       }

       return result;
    }
};

// 左右乘积列表plus
// 时间复杂度O(n)
// 空间复杂度O(1)，只要答案数组以外的空间才计算时间复杂度
class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
       int n = nums.size();

       vector<int> answer(n);
       // left_multi
       answer[0] = nums[0];
       for (int i = 1; i < n; ++i) {
          answer[i] = answer[i - 1] * nums[i];
       }

       int right_multi { 1 };
       for (int i = n - 1; i >= 0; --i) {
          if (i == 0) {
             answer[0] = 1 * right_multi;
             continue;
          }
          int temp = nums[i] * right_multi;
          answer[i] = answer[i - 1] * right_multi;
          right_multi = temp; 
       }

       return answer;
    }
};

int main() {
   Solution s;
   vector<int> input{ 1,2,3,4 };
   vector<int> result;
   result = s.productExceptSelf(input);
   int a = 0;
}

收获

掌握了这个题目的做法