這個問題在線性時間和空間中看起來很容易解決。這個問題建立在數組的一些基本概念之上。
在程式設計面試中提出這個問題的公司有 Facebook、亞馬遜、蘋果、Netflix、Google、微軟、Adobe 以及許多其他頂尖科技公司。
給定一個整數數組 nums，傳回一個數組 answer，使得 answer[i] 等於 nums 中除 nums[i] 之外的所有元素的乘積。
nums 的任何前綴或後綴的乘積保證適合32位元整數。
您必須編寫一個在 O(n) 時間內運作且不使用除法運算的演算法。
測試案例#1：
Input: nums = [1,2,3,4] Output: [24,12,8,6]
測試案例#2:
Input: nums = [-1,1,0,-3,3] Output: [0,0,9,0,0]
這個問題在線性時間和空間上看起來更容易解決，但在編寫偽代碼或實際程式碼實作時卻很棘手。
讓我們來看看包含 4 個元素的簡單陣列的預期結果：
input = {1, 2, 3, 4}
因此，每個索引處的值是數組中除該值本身之外的所有其他元素的乘積。下圖說明了這一點。
根據上圖，我們可以得到一個公式。對於任何給定的索引 i，我們可以使用從 o 到 (i - 1) 的元素的乘積加上從 (i 1) 到 (N - 1) 的元素的乘積來找到該值。如下圖：
在寫偽代碼之前，先提出問題並向面試官提問。
一旦你和麵試官討論了上述問題，就想出各種方法來解決問題。
要採用強力方法，我們必須執行兩個 for 迴圈。當外循環索引與內循環索引值相符時，我們應該跳過乘積；否則，我們將繼續使用該產品。
// brute force
static int[] bruteForce(int[] nums) {
int N = nums.length;
int[] result = new int[N];
for (int i = 0; i < N; i++) {
int currentProduct = 1;
for (int j = 0; j < N; j++) {
if (i == j) {
continue;
}
currentProduct *= nums[j];
}
result[i] = currentProduct;
}
return result;
}
大多數開發人員認為的一種方法是運行所有元素的乘積和，將乘積和除以每個數組值，然後返回結果。
// O(n) time and O(1) space p = 1 for i -> 0 to A[i] p * = A[i] for i -> 0 to (N - 1) A[i] = p/A[i] // if A[i] == 0 ? BAM error‼️
// code implementation
static int[] productSum(int[] nums) {
int product_sum = 1;
for(int num: nums) {
product_sum *= num;
}
for(int i = 0; i < nums.length; i++) {
nums[i] = product_sum/nums[i];
}
return nums;
}
如果陣列元素之一包含 0 怎麼辦？ ？
除了包含0的索引之外，所有索引的值肯定是無限大。另外，程式碼會拋出 java.lang.ArithmeticException。
Exception in thread "main" java.lang.ArithmeticException: / by zero
at dev.ggorantala.ds.arrays.ProductOfArrayItself.productSum(ProductOfArrayItself.java:24)
at dev.ggorantala.ds.arrays.ProductOfArrayItself.main(ProductOfArrayItself.java:14)
在我的網站上的數組掌握課程中了解有關前綴和後綴和的更多信息 https://ggorantala.dev
前綴和後綴是在為結果編寫演算法之前計算的。字首和字尾總和公式如下：
Function usingPrefixSuffix(nums):
N = length of nums
result = new array of length N
prefix_sum = new array of length N
suffix_sum = new array of length N
// Calculate prefix products
prefix_sum[0] = nums[0]
For i from 1 to N-1:
prefix_sum[i] = prefix_sum[i-1] * nums[i]
// Calculate suffix products
suffix_sum[N-1] = nums[N-1]
For i from N-2 to 0:
suffix_sum[i] = suffix_sum[i+1] * nums[i]
// Calculate result array
For i from 0 to N-1:
If i == 0:
result[i] = suffix_sum[i+1]
Else If i == N-1:
result[i] = prefix_sum[i-1]
Else:
result[i] = prefix_sum[i-1] * suffix_sum[i+1]
Return result
// using prefix and suffix arrays
private static int[] usingPrefixSuffix(int[] nums) {
int[] result = new int[nums.length];
int[] prefix_sum = new int[nums.length];
int[] suffix_sum = new int[nums.length];
// prefix sum calculation
prefix_sum[0] = nums[0];
for (int i = 1; i < nums.length; i++) {
prefix_sum[i] = prefix_sum[i - 1] * nums[i];
}
// suffix sum calculation
suffix_sum[nums.length - 1] = nums[nums.length - 1];
for (int i = nums.length - 2; i >= 0; i--) {
suffix_sum[i] = suffix_sum[i + 1] * nums[i];
}
for (int i = 0; i < nums.length; i++) {
if (i == 0) { // when variable `i` is at 0th index
result[i] = suffix_sum[i + 1];
} else if (i == nums.length - 1) { // when variable `i` is at last index
result[i] = prefix_sum[i - 1];
} else { // for all other indexes
result[i] = prefix_sum[i - 1] * suffix_sum[i + 1];
}
}
return result;
}
Each of these steps involves a single pass through the array, resulting in a total time complexity of O(n)+O(n)+O(n) = 3O(n), which is O(n).
For the suffix array calculation, we override the input nums array instead of creating one.
private static int[] usingPrefixSuffixOptimization(int[] nums) {
int[] result = new int[nums.length];
int[] prefix_sum = new int[nums.length];
// prefix sum calculation
prefix_sum[0] = nums[0];
for (int i = 1; i < nums.length; i++) {
prefix_sum[i] = prefix_sum[i - 1] * nums[i];
}
// suffix sum calculation, in-place - `nums` array override
for (int i = nums.length - 2; i >= 0; i--) {
nums[i] = nums[i + 1] * nums[i];
}
for (int i = 0; i < nums.length; i++) {
if (i == 0) { // when variable `i` is at 0th index
result[i] = nums[i + 1];
} else if (i == nums.length - 1) { // when variable `i` is at last index
result[i] = prefix_sum[i - 1];
} else { // for all other indexes
result[i] = prefix_sum[i - 1] * nums[i + 1];
}
}
return result;
}
Hence, we reduced the space of O(n). Time and space are not reduced, but we did a small optimization here.
This is a rather easy approach when we use the knowledge of prefix and suffix arrays.
For every given index i, we will calculate the product of all the numbers to the left and then multiply it by the product of all the numbers to the right. This will give us the product of all the numbers except the one at the given index i. Let's look at a formal algorithm that describes this idea more clearly.
Function prefixSuffix1(nums):
N = length of nums
result = new array of length N
prefix_sum = new array of length N
suffix_sum = new array of length N
// Calculate prefix products
prefix_sum[0] = 1
For i from 1 to N-1:
prefix_sum[i] = prefix_sum[i-1] * nums[i-1]
// Calculate suffix products
suffix_sum[N-1] = 1
For i from N-2 to 0:
suffix_sum[i] = suffix_sum[i+1] * nums[i+1]
// Calculate result array
For i from 0 to N-1:
result[i] = prefix_sum[i] * suffix_sum[i]
Return result
private static int[] prefixSuffixProducts(int[] nums) {
int[] result = new int[nums.length];
int[] prefix_sum = new int[nums.length];
int[] suffix_sum = new int[nums.length];
prefix_sum[0] = 1;
for (int i = 1; i < nums.length; i++) {
prefix_sum[i] = prefix_sum[i - 1] * nums[i - 1];
}
suffix_sum[nums.length - 1] = 1;
for (int i = nums.length - 2; i >= 0; i--) {
suffix_sum[i] = suffix_sum[i + 1] * nums[i + 1];
}
for (int i = 0; i < nums.length; i++) {
result[i] = prefix_sum[i] * suffix_sum[i];
}
return result;
}
Each of these steps involves a single pass through the array, resulting in a total time complexity of O(n)+O(n)+O(n) = 3O(n), which is O(n).
All three arrays are of length n, so the total space complexity is O(n) + O(n) + O(n) = 3O(n), which is O(n).
The carry forward technique optimizes us to solve the problem with a more efficient space complexity. Instead of using two separate arrays for prefix and suffix products, we can use the result array itself to store intermediate results and use a single pass for each direction.
Here’s how you can implement the solution using the carry-forward technique:
prefix products
prefixProduct = 1
For i from 0 to N-1:
result[i] = prefixProduct
prefixProduct = prefixProduct * nums[i]
// Calculate suffix products and finalize result
suffixProduct = 1
For i from N-1 to 0:
result[i] = result[i] * suffixProduct
suffixProduct = suffixProduct * nums[i]
Return result
// carry forward technique
private static int[] carryForward(int[] nums) {
int n = nums.length;
int[] result = new int[n];
// Calculate prefix products
int prefixProduct = 1;
for (int i = 0; i < n; i++) {
result[i] = prefixProduct;
prefixProduct *= nums[i];
}
// Calculate suffix products and finalize the result
int suffixProduct = 1;
for (int i = n - 1; i >= 0; i--) {
result[i] *= suffixProduct;
suffixProduct *= nums[i];
}
return result;
}
This approach uses only a single extra array (result) and two variables (prefixProduct and suffixProduct), achieving efficient space utilization while maintaining O(n) time complexity.
以上是Leetcode：除自身之外的陣列的乘積的詳細內容。更多資訊請關注PHP中文網其他相關文章！
