- Given an array nums of n integers where n > 1, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].
- Example:
- Input: [1,2,3,4]
- Output: [24,12,8,6]
- Note: Please solve it without division and in O(n).
- Follow up:
- Could you solve it with constant space complexity? (The output array does not count as extra space for the purpose of space complexity analysis.)
- public class Solution {
- public int[] productExceptSelf(int[] nums) {
- int n = nums.length;
- int[] res = new int[n];
- res[0] = 1;
- for (int i = 1; i <n; i++) {
- res[i] = res[i - 1] * nums[i - 1];
- }
- int right = 1;
- for (int i = n - 1; i>= 0; i--) {
- res[i] *= right;
- right *= nums[i];
- }
- return res;
- }
- public int[] productExceptSelf(int[] nums) {
- // Left is an array containing the left products
- // i.e: left[i] = nums[0] * .... * nums[i-1]
- int[] left = new int[nums.length];
- // Right is an array containing the array products
- //i.e: right[i] = nums[i+1] * nums[i+2] * .... * nums[len(nums) - 1]
- int[] right = new int[nums.length];
- left[0] = 1;
- for (int i = 1; i <nums.length; i++) {
- left[i] = left[i-1] * nums[i-1];
- }
- right[nums.length - 1] = 1;
- for (int i = nums.length - 2; i>= 0; i--) {
- right[i] = right[i+1] * nums[i+1];
- }
- int[] product = new int[nums.length];
- for (int i = 0; i < product.length; i++) {
- product[i] = left[i] * right[i];
- }
- return product;
- }
- }
来源: http://www.bubuko.com/infodetail-3400479.html