数组元素的最小非零乘积
难度:
标签:
题目描述
代码结果
运行时间: 15 ms, 内存: 16.0 MB
// Java Stream Solution
/*
* 思路:
* 1. 计算 nums 的乘积和最低非零乘积。
* 2. 利用 Java Stream 处理 nums 元素。
* 3. 使用 bit manipulation 技术确保低位和高位交换。
*/
import java.util.stream.LongStream;
public class StreamSolution {
private static final int MOD = 1000000007;
public int minNonZeroProduct(int p) {
long maxNum = (1L << p) - 1;
long half = maxNum / 2;
long minProduct = (maxNum % MOD) * LongStream.iterate(maxNum - 1, n -> n - 1).limit(half).reduce(1L, (a, b) -> (a * b) % MOD) % MOD;
return (int) minProduct;
}
}
解释
方法:
题解的思路是基于数学推导和观察。给定一个正整数p,数组nums包含了从1到2^p - 1的所有整数。要得到最小非零乘积,可以考虑将nums数组中的最大值(2^p - 1)与其余较小值的乘积最小化。由于可以通过位交换自由地调整nums中的任意两个数,观察到当nums中最大值(2^p - 1)保持不变,其余所有的数(从1到2^p - 2)都设置为次大值(2^p - 2)时,可以得到最小乘积。因此,问题转化为计算(2^p - 2)^(2^(p-1) - 1) * (2^p - 1) % (10^9 + 7)。这个公式的推导基于组合数学中的排列组合理论,考虑到位操作的自由度和模运算的性质。
时间复杂度:
O(log(2^(p-1))) 或 O(p)
空间复杂度:
O(1)
代码细节讲解
🦆
为什么选择将数组中的最大值保持不变而将其他值设置为次大值,这样的操作如何保证得到的乘积是最小的?
▷🦆
在题解中提到可以自由通过位交换调整nums中的任意两个数,这种操作的具体步骤是什么?能否通过一个具体的例子说明如何通过位交换达到预期的数组状态?
▷🦆
题解中的公式`(2^p - 2)^(2^(p-1) - 1) * (2^p - 1) % (10^9 + 7)`是如何推导出来的?请解释其中每个组成部分的意义及其在问题中的角色。
▷