ToB企服应用市场:ToB评测及商务社交产业平台

标题: LeetCode刷题记录——day2 [打印本页]

---

作者: 东湖之滨    时间: 2024-5-14 21:12
标题: LeetCode刷题记录——day2
https://leetcode.cn/problems/product-of-array-except-self/description/?envType=study-plan-v2&envId=top-interview-150
问题在于不利用除法并且空间复杂度为O(1)，当第一次重新开始遍历时由于不知道后续数组元素是什么，所以无法得到答案，而如果当知道一个后续数组元素后，又回去更新答案的话，无疑会提高时间复杂度。不妨这样看待，如果我们已经遍历一次数组并且可以或许记录下足够的信息的话，那么下次我们再次遍历数组时不就可以相对地知道后续元素的信息了吗。由此推广，为了算法简单一些，我们甚至可以遍历有限次，获得足够的信息，然后一次得到最终答案。
由这样的思路我们再看问题，对于任何一个元素，其除了自身以外的的元素的乘积由两个部分构成，一个是它的前序元素乘积，一个是后续元素乘积。前者可以通过正向的遍历得到，后者通过反向遍历也可以得到，由此答案就明了了；
[code]class Solution {public:    vector productExceptSelf(vector& nums) {        int len = nums.size();        vector answer(len);        int answer_R[len],answer_L[len];        answer_L[0]=1,answer_R[len-1]=1;        for(int i=1;i=0;i--){            answer_R=answer_R[i+1]*nums[i+1];        }        for(int i=0;i

---

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)

Powered by Discuz! X3.4