Given an array of n integers where n > 1, nums, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].
Solve it without division and in O(n).
For example, given [1,2,3,4], return [24,12,8,6].
Follow up:
Could you solve it with constant space complexity? (Note: The output array does not count as extra space for the purpose of space complexity analysis.)
有三种情况:
数组元素不含0,像[1,2,3,4], return [24,12,8,6]
数组元素有1个0,[1,0,3,4], return [0,12,0,0],是0的那个位置是其他元素的乘积
数组元素有2个或者2个以上0,[1,0,0,4]则返回[0,0,0,0],返回全部是0.
public class ProductArrayExceptSelf { public int[] solution(int[] nums) { int zeroCount = 0; for (int n : nums) if (n == 0) zeroCount++; // 有两个或者两个以上的元素是0,那么数组设为全零返回 if (zeroCount > 1) { for (int i = 0; i < nums.length; i++) nums[i] = 0; } else if (zeroCount == 0) { // 如果没有0,则计算所有的乘积 int product = 1; for (int n : nums) product *= n; // 每个数组元素置为product / 该位置值即可 for (int i = 0; i < nums.length; i++) nums[i] = product / nums[i]; } else { // 如果元素中有1个0 int product = 1; // 跳过那个元素,计算所有的乘积 for (int n : nums) if (n != 0) product *= n; // 元素为0的位置置为product,其他置为0 for (int i = 0; i < nums.length; i++) if (nums[i] == 0) nums[i] = product; else nums[i] = 0; } return nums; } public static void main(String[] args) { System.out.println(Arrays.toString(new ProductArrayExceptSelf().solution(new int[] { 1, 0, 3, 0 }))); } }
补上one pass 且不用除法, o(n)解法。
使用左右指针,一遍遍历即可
public int[] solution2(int[] nums) { int[] result = new int[nums.length]; Arrays.fill(result, 1); int left = 1, right = 1; int len = nums.length; for (int i = 0; i < len; i++) { result[i] *= left; result[len - 1 - i] *= right; left *= nums[i]; right *= nums[len - i - 1]; //System.out.println(Arrays.toString(result)); } return result; }
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/66760.html
摘要:题目描述题目解析简单来说就是对于数组中每一项,求其他项之积。算一遍全部元素的积再分别除以每一项要仔细考虑元素为零的情况。没有零直接除下去。一个零零的位置对应值为其他元素之积,其他位置为零。两个以上的零全部都是零。 题目描述 Given an array of n integers where n > 1, nums, return an array output such that o...
Problem Given an array of n integers where n > 1, nums, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i]. Solve it without division and in ...
问题:Given an array of n integers where n > 1, nums, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i]. Solve it without division and in O(n)....
Problem Given an array of n integers where n > 1, nums, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i]. Solve it without division and in ...
摘要:动态规划复杂度时间空间思路分析出自身以外数组乘积的性质,它实际上是自己左边左右数的乘积,乘上自己右边所有数的乘积。所以我们可以用一个数组来表示第个数字前面数的乘积,这样。同理,我们可以反向遍历一遍生成另一个数组。 Product of Array Except Self Given an array of n integers where n > 1, nums, return an...
阅读 3401·2023-04-26 02:48
阅读 1428·2021-10-11 10:57
阅读 2446·2021-09-23 11:35
阅读 1166·2021-09-06 15:02
阅读 3268·2019-08-30 15:54
阅读 1573·2019-08-30 15:44
阅读 850·2019-08-30 15:44
阅读 957·2019-08-30 12:52