この問題は線形時間と空間で解くのが簡単そうに見えます。この問題は、配列の基本的な概念のいくつかに基づいています。
コーディング面接でこの質問をした企業は、Facebook、Amazon、Apple、Netflix、Google、Microsoft、Adobe、その他多くのトップテクノロジー企業です。
整数配列 nums を指定すると、answer[i] が nums[i] を除く nums のすべての要素の積と等しくなるような配列の回答を返します。
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) までの要素の積を使用して値を見つけることができます。これを次の図に示します。
疑似コードを書く前に、質問を考えて面接官に質問してください。
あなたと面接官が上記の質問について話し合ったら、問題を解決するためのさまざまなアプローチを考案してください。
総当たりアプローチを採用するには、2 つの 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;
}
ほとんどの開発者が考える 1 つの方法は、すべての要素の積和を実行し、その積和を各配列値で除算して、結果を返すことです。
// 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;
}
配列要素の 1 つに 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)
プレフィックスとサフィックスの合計について詳しくは、私の Web サイト 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 : Self を除く配列の積の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。
![[Web フロントエンド] Node.js クイック スタート](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
