leetcode
leetcode 1751 ~ 1800
数组元素的最小非零乘积

数组元素的最小非零乘积

难度:

标签:

题目描述

代码结果

运行时间: 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)

代码细节讲解

🦆
为什么选择将数组中的最大值保持不变而将其他值设置为次大值,这样的操作如何保证得到的乘积是最小的?
在给定的问题中,要最小化最大值(2^p - 1)与其他数的乘积。由于乘积的大小直接受到乘数大小的影响,选择次大值(2^p - 2)作为其他数,可以有效减小乘积的大小。这种选择是因为2^p - 2接近于2^p - 1,而其他较小的数如1, 2, ..., 这些数与2^p - 1的乘积将会更大。因此,将其他值设置为次大值可以最小化整体乘积,从而得到题目要求的最小非零乘积。
🦆
在题解中提到可以自由通过位交换调整nums中的任意两个数,这种操作的具体步骤是什么?能否通过一个具体的例子说明如何通过位交换达到预期的数组状态?
题解中的位交换可能指的是理论上的操作,意在说明我们可以考虑数组中任意两数的组合。实际应用中,并非通过直接的位交换来调整数组。例如,对于p=3的情况,原数组为[1, 2, 3, 4, 5, 6, 7],最大值为7,次大值为6。题目理论上假设我们可以将数组调整为[6, 6, 6, 6, 6, 6, 7],通过这样的调整来最小化乘积。这种调整实际上是从数学角度简化问题,而非真实执行位交换。
🦆
题解中的公式`(2^p - 2)^(2^(p-1) - 1) * (2^p - 1) % (10^9 + 7)`是如何推导出来的?请解释其中每个组成部分的意义及其在问题中的角色。
这个公式的推导基于以下思考:考虑到数组中最大值为2^p - 1,其余都调整为次大值2^p - 2。数组中从1到2^p - 1的数的总数是2^p - 1个,因此除了最大值外,有2^p - 2个数。由于我们将这些数都调整为次大值,每个数出现的次数为2^(p-1) - 1(因为总数为2^(p-1), 减去一个最大值)。因此,我们需要计算次大值的这么多次幂,再乘以最大值。最后,由于结果需要在模10^9 + 7的条件下进行,因此整个表达式需要取模。

相关问题