给定一个长度为 n 的数组 nums ,返回一个数组 res,res[i]是nums数组中除了nums[i]本身以外其余所有元素的乘积,即:
1.请不要使用除法,并且在 O(n) 时间复杂度内完成此题。
2.题目数据保证res数组的元素都在 32 位整数范围内。
3.有O(1)空间复杂度的做法,返回的res数组不计入空间复杂度计算。
数据范围:
[1,2,3,4]
[24,12,8,6]
res[0]=2*3*4=24 res[1]=1*3*4=12 res[2]=1*2*4=8 res[3]=1*2*3=6
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param nums int整型一维数组 * @return int整型一维数组 */ public int[] timesExceptSelf (int[] nums) { // left和right数组可以通过下表变换,一次遍历就求出来 int n = nums.length; int[] left = new int[n]; int[] right = new int[n]; left[0] = 1; right[n - 1] = 1; for(int i = 1; i < n; i++){ left[i] = nums[i - 1] * left[i - 1]; right[n - 1 - i] = nums[n - i] * right[n - i]; } // 为了节省空间,直接把right数组的元素乘到left数组上,将left数组作为结果返回 for(int i = 0; i < n; i++){ left[i] *= right[i]; } return left; } }
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param nums int整型vector * @return int整型vector */ vector<int> timesExceptSelf(vector<int>& nums) { // write code here int n = nums.size(); vector<int> res(n, 1); vector<int> res2(n, 1); // 保存从右往左的乘积 加入输入是 1 2 3 4 // 对应的输出就是 24 12 4 1 for(int i=n-2; i>=0; i--) { res[i] = res[i+1] * nums[i+1]; } // 保存的是从左往右的乘积 假如输入的是 1 2 3 4 // 输出是 1 1 2 6 for(int i=1; i<n; i++) { res2[i] = res2[i-1] * nums[i-1]; } // 从左往右的值 乘上 从右往左 就是最后的输出结果 for(int i=0; i<n; i++) { res[i] = res[i] * res2[i]; } return res; } };
# # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param nums int整型一维数组 # @return int整型一维数组 # class Solution: def timesExceptSelf(self , nums: List[int]) -> List[int]: # write code here dp_l = nums.copy() for i in range(1, len(dp_l)): dp_l[i] = dp_l[i-1] * nums[i] dp_r = nums.copy() for i in range(len(dp_r)-1 -1, -1, -1): dp_r[i] = dp_r[i + 1] * nums[i] res = nums.copy() res[0] = dp_r[1] res[-1] = dp_l[-2] for i in range(1, len(nums)-1): res[i] = dp_l[i-1] * dp_r[i + 1] return res
# # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param nums int整型一维数组 # @return int整型一维数组 # class Solution: def timesExceptSelf(self , nums: List[int]) -> List[int]: reslist = [] pro = 1 count = nums.count(0) for i in nums: if i != 0: pro *= i if count == 0: for i in nums: reslist.append(pro//i) elif count == 1: for i in nums: if i != 0: reslist.append(0) elif i == 0: reslist.append(pro) else: for i in nums: reslist.append(0) return reslist # write code here
package main /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param nums int整型一维数组 * @return int整型一维数组 */ func timesExceptSelf( nums []int ) []int { pre:=1 ans:=make([]int,len(nums)) for i:=0;i<len(nums);i++{ ans[i]=pre pre*=nums[i] } pre=1 for i:=len(nums)-1;i>=0;i--{ ans[i]*=pre pre*=nums[i] } return ans }
#include <vector> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param nums int整型vector * @return int整型vector */ vector<int> timesExceptSelf(vector<int>& nums) { // write code here int length=nums.size(); vector<int> left(length, 1); vector<int> right(length, 1); vector<int> result(length); left[0]=1, right[length-1]=1; for(int i=1;i<length;i++) { left[i]=left[i-1]*nums[i-1]; } for(int i=length-2;i>=0;i--) { right[i]=right[i+1]*nums[i+1]; } for(int i=0;i<length;i++) { result[i]=left[i]*right[i]; } return result; } };
public int[] timesExceptSelf (int[] nums) { // write code here int len = nums.length; int[] res = new int[len]; res[len - 1] = 1; res[0] = 1; for (int i = len - 2; i >= 0; i--) { res[i] = res[i + 1] * nums[i + 1]; } for (int i = 1; i < len - 1; i++) { nums[i] = nums[i] * nums[i - 1]; } // System.out.println(Arrays.toString(res)); // System.out.println(Arrays.toString(nums)); for (int i = 1; i < len; i++) { res[i] = res[i] * nums[i - 1]; } return res; }
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param nums int整型一维数组 * @return int整型一维数组 */ public int[] timesExceptSelf (int[] nums) { // write code here int[] res = new int[nums.length]; res[0] = 1; for(int i = 1; i < nums.length; i++){ res[i] = res[i - 1] * nums[i - 1]; } int temp = 1; for(int i = nums.length - 1; i >=0; i--){ res[i] = temp * res[i]; temp = temp * nums[i]; } return res; } }
空间复杂度为O(1),时间复杂度为O(n)
实际上返回数组是可以重复利用的,不必用两个数组
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param nums int整型vector * @return int整型vector */ vector timesExceptSelf(vector& nums) { // write code here int n = nums.size(); if(nums.size() < 2) return nums; vector res; res.push_back(1); int temp; for(int i = 1;i < n;++i) { temp = res[i-1] * nums[i-1]; res.push_back(temp); } temp = nums[n-1]; for(int i = n-2;i > 0;--i) { res[i] *= temp; temp *= nums[i]; } temp = 1; for(int i = 1;i < n;++i) { temp *= nums[i]; } res[0] = temp; return res; } };
public int[] timesExceptSelf (int[] nums) { int n=nums.length; int preTime[]=new int[n]; int postTime[]=new int[n]; postTime[n-1]=1; preTime[0]=1; int result[]=new int[n]; //倒着各元素的乘积 for(int i=n-2;i>=0;i--){ postTime[i]=postTime[i+1]*nums[i+1]; } //顺着各元素的乘积 for(int i=1;i<n;i++){ preTime[i]=preTime[i-1]*nums[i-1]; result[i]=preTime[i]*postTime[i]; } result[0]=postTime[0]; return result; }