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.)
有三種情況:
數(shù)組元素不含0,像[1,2,3,4], return [24,12,8,6]
數(shù)組元素有1個0,[1,0,3,4], return [0,12,0,0],是0的那個位置是其他元素的乘積
數(shù)組元素有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,那么數(shù)組設(shè)為全零返回 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; // 每個數(shù)組元素置為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; }
文章版權(quán)歸作者所有,未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址:http://specialneedsforspecialkids.com/yun/66760.html
摘要:題目描述題目解析簡單來說就是對于數(shù)組中每一項,求其他項之積。算一遍全部元素的積再分別除以每一項要仔細考慮元素為零的情況。沒有零直接除下去。一個零零的位置對應(yīng)值為其他元素之積,其他位置為零。兩個以上的零全部都是零。 題目描述 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 ...
摘要:動態(tài)規(guī)劃復(fù)雜度時間空間思路分析出自身以外數(shù)組乘積的性質(zhì),它實際上是自己左邊左右數(shù)的乘積,乘上自己右邊所有數(shù)的乘積。所以我們可以用一個數(shù)組來表示第個數(shù)字前面數(shù)的乘積,這樣。同理,我們可以反向遍歷一遍生成另一個數(shù)組。 Product of Array Except Self Given an array of n integers where n > 1, nums, return an...
閱讀 3461·2023-04-26 02:48
閱讀 1465·2021-10-11 10:57
閱讀 2490·2021-09-23 11:35
閱讀 1196·2021-09-06 15:02
閱讀 3294·2019-08-30 15:54
閱讀 1612·2019-08-30 15:44
閱讀 879·2019-08-30 15:44
閱讀 988·2019-08-30 12:52