晋城市建设局网站安全证查询官网

晋城市建设局网站,安全证查询官网,公司名称起名大全免费,郑东新区网站开发思路#xff1a;一、前后缀分解1.answer[i]等于nums中除了nums[i]之外的其余各元素的乘积。换句话说#xff0c;如果知道了i左边所有数的乘积#xff0c;以及i右边所有数的乘积#xff0c;就可以算出answer[i]。2.定义pre[i]和post[i]#xff1a;#xff08;1#xff09…思路一、前后缀分解1.answer[i]等于nums中除了nums[i]之外的其余各元素的乘积。换句话说如果知道了i左边所有数的乘积以及i右边所有数的乘积就可以算出answer[i]。2.定义pre[i]和post[i]1定义pre[i]表示从nums[0]到nums[i -1]的乘积。2定义post[i]表示从nums[i 1]到nums[n - 1]的乘积。3.计算pre[i]和post[i]1要计算pre[i]可以先计算出nums[0]到nums[2]的乘积pre[i - 1]再乘上nums[i - 1]就得到了pre[i]。即pre[i] pre[i - 1] * nums[i - 1]。2同理可得post[i] post[i 1] * nums[i 1]。4.设置初始值pre[0] post[n - 1] 1。5.所求结果answer[i] pre[i] * post[i]。6.复杂度分析1时间复杂度O(n)其中n是nums的长度。2空间复杂度O(n)。附代码class Solution { public int[] productExceptSelf(int[] nums) { int n nums.length; int[] pre new int[n]; pre[0] 1; for(int i 1;i n;i){ pre[i] pre[i - 1] * nums[i - 1]; } int[] post new int[n]; post[n - 1] 1; for(int i n - 2;i 0;i--){ post[i] post[i 1] * nums[i 1]; } int[] ans new int[n]; for(int i 0;i n;i){ ans[i] pre[i] * post[i]; } return ans; } }二、优化先后缀分解不使用额外空间1.思路先计算post然后一边计算pre一边把pre直接乘到post[i]中最后返回post。由于题目中说明输出数组不被视为额外空间所以该做法的空间复杂度为O(1)。此外这种做法可以少遍历一次。2.复杂度分析1时间复杂度O(n)其中n是nums的长度。2空间复杂度O(1)返回值不计入。附代码class Solution { public int[] productExceptSelf(int[] nums) { int n nums.length; int[] post new int[n]; post[n - 1] 1; for(int i n - 2;i 0;i--){ post[i] post[i 1] * nums[i 1]; } int pre 1; for(int i 0;i n;i){ //此时pre为nums[0]到nums[i - 1]的乘积可以直接乘到post[i]中 post[i] * pre; pre * nums[i]; } return post; } }