day14 除自身以外数组的乘积

时间好紧张。

读题

给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。
请 不要使用除法， 且在 O(n) 时间复杂度内完成此题。

思路

如果可以使用除法，那么计算总乘积后除以当前的数即可；但是禁止使用除法。
精度问题应该不需要考虑。
如果是暴力，每个位置的数都遍历一边其他数，那很傻。
要求时间 O(n)，因此遍历一遍。设想是否能使用 dp？
要想使用 dp，需要有初始条件，递推公式。初始条件不知道，但递推公式是可以得到的，需要有 answer[i]、answer[i-1]、answer[i+1]的关系。
有 answer[i]×nums[j] = answer[j]×nums[i]

1. 创建新数组 answer，初始化为全部为 1
2. 处理首个元素
3. 递推，对于第 i 个元素：

---

值得注意的是，题目给定了 nums 里数字的范围，是-30 到 30，一个较小的范围。那么问题可以变成和上一道题类似的思路了：首先计数，然后乘。

1. 计数：
   1. 创建一个 map，遍历记录每一个数字出现的次数
2. 乘积
   1. 幂运算

时间复杂度大概是 mn？

于是有代码：

#include <math.h>
class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int length_nums = nums.size();
        map<int, int> nums_count;
        vector<int>answer(length_nums, 1);
        for(int& num:nums){
            nums_count[num]++;
        }
        int i=0;
        for(int i=0;i<length_nums;i++){
            for (auto it = nums_count.begin(); it != nums_count.end(); ++it) {
                // answer[i]*=it->first*(nums[i]==it->first?it->second-1:it->second);
                if(nums[i]==it->first){
                    if(it->second > 1)
                        answer[i]*=pow(it->first,it->second-1);
                }else
                    answer[i]*=pow(it->first,it->second);
            }
        }
        return answer;
    }
};

结果

通过了，11 ms，39.61 mb。时间比较长，大部分解法都是 0 ms 的。
时间复杂度应该是 O(mn) ，其中 m 最大为 61。四舍五入也是 O(n)，
空间复杂度是 O(n)，要求的是 O(1)。

官方题解

方法一 ：左右乘积列表

官方思路
我们不必将所有数字的乘积除以给定索引处的数字得到相应的答案，而是利用索引左侧所有数字的乘积和右侧所有数字的乘积（即前缀与后缀）相乘得到答案。
对于给定索引 i，我们将使用它左边所有数字的乘积乘以右边所有数字的乘积。下面让我们更加具体的描述这个算法。
算法

1. 初始化两个空数组 L 和 R。对于给定索引 i，L[i] 代表的是 i 左侧所有数字的乘积，R[i] 代表的是 i 右侧所有数字的乘积。
2. 我们需要用两个循环来填充 L 和 R 数组的值。对于数组 L，L[0] 应该是 1，因为第一个元素的左边没有元素。对于其他元素：L[i] = L[i-1] * nums[i-1]。
3. 同理，对于数组 R，R[length-1] 应为 1。Length 指的是输入数组的大小。其他元素：R[i] = R[i+1] * nums[i+1]。
4. 当 R 和 L 数组填充完成，我们只需要在输入数组上迭代，且索引 i 处的值为：L[i] * R[i]。

---

是的，这就是我一直求而不得的那个 “dp” 做法。我希望能找到前后关系用于完成 answer 的填充，但是我发现单向前进时，只能得到无限个后面的数字乘积，和有限个前面的数字乘积。
这里的解决办法是走两边，一遍正向一遍后向。
很简单，也很高明。时间复杂度是 n，空驾复杂度也是 n。

如何令空间复杂度为 O (1)

可以将 L 或 R 数组用输出数组来计算。先把输出数组当作 L 数组来计算，然后再动态构造 R 数组得到结果

评论区解法

双指针。
我怎么忘了你呢？
（虽然还是两遍历）

收获

太神奇了算法。