資訊專欄INFORMATION COLUMN
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個(gè)0，[1,0,3,4], return [0,12,0,0]，是0的那個(gè)位置是其他元素的乘積
數(shù)組元素有2個(gè)或者2個(gè)以上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++;
// 有兩個(gè)或者兩個(gè)以上的元素是0，那么數(shù)組設(shè)為全零返回
if (zeroCount > 1) {
for (int i = 0; i < nums.length; i++)
nums[i] = 0;
} else if (zeroCount == 0) {
// 如果沒有0，則計(jì)算所有的乘積
int product = 1;
for (int n : nums)
product *= n;
// 每個(gè)數(shù)組元素置為product / 該位置值即可
for (int i = 0; i < nums.length; i++)
nums[i] = product / nums[i];
} else {
// 如果元素中有1個(gè)0
int product = 1;
// 跳過那個(gè)元素，計(jì)算所有的乘積
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 })));
}
}
補(bǔ)上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)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/66760.html
摘要：題目描述題目解析簡(jiǎn)單來說就是對(duì)于數(shù)組中每一項(xiàng)，求其他項(xiàng)之積。算一遍全部元素的積再分別除以每一項(xiàng)要仔細(xì)考慮元素為零的情況。沒有零直接除下去。一個(gè)零零的位置對(duì)應(yīng)值為其他元素之積，其他位置為零。兩個(gè)以上的零全部都是零。 題目描述 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 ...
摘要：動(dòng)態(tài)規(guī)劃復(fù)雜度時(shí)間空間思路分析出自身以外數(shù)組乘積的性質(zhì)，它實(shí)際上是自己左邊左右數(shù)的乘積，乘上自己右邊所有數(shù)的乘積。所以我們可以用一個(gè)數(shù)組來表示第個(gè)數(shù)字前面數(shù)的乘積，這樣。同理，我們可以反向遍歷一遍生成另一個(gè)數(shù)組。 Product of Array Except Self Given an array of n integers where n > 1, nums, return an...
閱讀 3481·2023-04-26 02:48
閱讀 1474·2021-10-11 10:57
閱讀 2499·2021-09-23 11:35
閱讀 1207·2021-09-06 15:02
閱讀 3306·2019-08-30 15:54
閱讀 1623·2019-08-30 15:44
閱讀 891·2019-08-30 15:44
閱讀 997·2019-08-30 12:52
