238题:除自身以外数组的乘积
写作背景:由于最近在练习leetcode,这道题刚开始思路不太清晰,所以将自己的解题思路记录下来,以便后续复习。
题目描述:
解题思路:
- 1.暴力解法:遍历数组,每次遍历时,将当前元素置为1,然后遍历数组,将其他元素相乘,得到结果,将结果放入结果数组中,时间复杂度为O(n^2)
- 2.优化解法:遍历一遍数组,得到数组的乘积,然后遍历数组,将数组的乘积除以当前元素,得到结果,将结果放入结果数组中,时间复杂度为O(n)
- 难点:不能使用除法,且时间复杂度为O(n)
- 解决思路:使用乘积倒数来计算结果。
public class P238 {
public int[] productExceptSelf(int[] nums) {
if (nums.length == 0){
return nums;
}
int sumMultiply = 1;
int[] res = new int[nums.length];
int zeroCount = 0;
int zeroPos = -1;
for (int i = 0;i< nums.length;i++) {
if (0 != nums[i])
sumMultiply *= nums[i];
else {
zeroCount++;
zeroPos = i;
}
}
if (zeroCount > 1)
return res;
else if (zeroCount == 1) {
res[zeroPos] = sumMultiply;
return res;
}else {
for (int i = 0;i<nums.length;i++) {
res[i] = (int) (sumMultiply * calculateReciprocal(nums[i]));
}
}
return res;
}
// 计算一个数的倒数
private static double calculateReciprocal(int val) {
if (val == 0) {
return 0;
}
boolean negative = false;
// 判断是否是负数
if (val < 0) {
negative = true;
val = -val;
}
int iniVal = 1;
double iniInt = 1.0;
double iniDouble = 0.1;
double finalVal = 0.0;
int maxAcc = 16;
int iniAcc = 0;
do {
int count = 0;
// 将 iniInt 和 iniVal 调整到适当的范围
while (iniVal < val) {
iniVal *= 10;
iniInt *= iniDouble;
}
// 计算倒数的整数部分
while (iniVal >= val) {
iniVal -= val;
count++;
}
// 累加整数部分
finalVal += iniInt * count;
iniAcc++;
} while (iniVal != 0 && iniAcc < maxAcc);
return negative ? -finalVal : finalVal;
}
}
- 3.还可以通过数学方法计算一个数倒数并且不涉及除法,解决方法:使用对数来计算倒数,即:1/x = e^(-ln(x)),这样就可以使用乘积倒数来计算结果。
但是此方法由于java中的double类型精度问题,导致结果不准确,所以不推荐使用,但是可以作为一种思路。
public class P238 {
public int[] productExceptSelf(int[] nums) {
if (nums.length == 0){
return nums;
}
int sumMultiply = 1;
int[] res = new int[nums.length];
int zeroCount = 0;
int zeroPos = -1;
for (int i = 0;i< nums.length;i++) {
if (0 != nums[i])
sumMultiply *= nums[i];
else {
zeroCount++;
zeroPos = i;
}
}
if (zeroCount > 1)
return res;
else if (zeroCount == 1) {
res[zeroPos] = sumMultiply;
return res;
}else {
for (int i = 0;i<nums.length;i++) {
res[i] = (int) (sumMultiply * calculateReciprocal(nums[i]));
}
}
return res;
}
// 计算一个数的倒数
private static double calculateReciprocal(int val) {
if (val == 0) {
return 0;
}
boolean negative = false;
// 判断是否是负数
if (val < 0) {
negative = true;
val = -val;
}
return negative ? -Math.exp(-Math.log(val)) : Math.exp(-Math.log(val));
}
}