给定一个长度为 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
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; } }
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; }
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; } }