本文主要是介绍【每日一题】数组元素的最小非零乘积，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
文章目录
- Tag
- 题目来源
- 解题思路
- 方法一：贪心
- 写在最后
Tag
【贪心】【快速幂】【数组】【2024-03-20】
题目来源
1969. 数组元素的最小非零乘积
解题思路
方法一：贪心
前言
我们首先来思考一个简单的问题：假设给定三个整数 a a a， b b b， c c c，满足 1 < = a < b < c 1 <=a < b <c 1<=a<b<c，此时需要将某个数缩小 1，另外一个数增加 1，使得 abc 最小，如恶化选择才能最优？
- 缩小时 优先缩小最小 的元素：当选择 a a a 缩小
1，此时三者乘积为 ( a − 1 ) b c (a-1)bc (a−1)bc；当选择 b b b 缩小1，此时三者乘积为 a ( b − 1 ) c a(b-1)c a(b−1)c；当选择 c c c 缩小1，此时三者乘积为 a b ( c − 1 ) ab(c-1) ab(c−1)。比较三者有 ( a − 1 ) b c < a ( b − 1 ) c < a b ( c − 1 ) (a-1)bc < a(b-1)c < ab(c-1) (a−1)bc<a(b−1)c<ab(c−1)，所以为了使乘积最小，选择缩小最小的元素。 - 增加时 优先增加最大 的元素：此时已经选择了缩小 a a a。当选择 b b b 增加
1，此时三者乘积为 ( a − 1 ) ( b + 1 ) c (a-1)(b+1)c (a−1)(b+1)c；当选择 c c c 增加1，此时三者乘积为 ( a − 1 ) b ( c + 1 ) (a-1)b(c+1) (a−1)b(c+1)。比较二者有 ( a − 1 ) ( b + 1 ) c ≤ ( a − 1 ) b ( c + 1 ) (a-1)(b+1)c \le (a-1)b(c+1) (a−1)(b+1)c≤(a−1)b(c+1)，所以为了使乘积最小，选择增加最大的元素。
位交换的本质
在本题中，将两个数对应的二进制数相同的位进行交换，本质上是将一个数缩小 2 k 2^k 2k，另一个数增加 2 k 2^k 2k，其中 k 是交换的第几位（二进制数从低位向高位方向数，从 0 开始数）。可以自行举例子加以理解。
示例分析
根据以上分析，我们可以知道一种贪心思路：进行相同位交换时，优先缩小数组中的自小元素，再增加数组中的最大元素。
设当前数组位 [ 1 , 2 , 3 , . . . , 2 p − 2 , 2 p − 1 ] [1, 2, 3, ..., 2^p-2, 2^p-1] [1,2,3,...,2p−2,2p−1]，缩小时按照从小到大考虑每个元素：
- 首先考虑缩小
1，此时需要将 1 减少1，此时从右向左依次考虑最大的元素，由于 2 p − 1 2p−1 2p−1 每一位均为1无法再增加；接着考虑 2 p − 2 2^p-2 2p−2，此时将最低位变为1，数组变为： [ 0 , 2 , 3 , ⋯ , 2 p − 3 , 2 p − 1 , 2 p − 1 ] [0, 2, 3, ⋯ , 2p−3, 2p−1, 2p−1] [0,2,3,⋯ ,2p−3,2p−1,2p−1]； - 接着考虑缩小
2，此时需要将 2 减少2，此时从右向左依次考虑最大的元素，由于 2 p − 1 2p−1 2p−1 每一位均为1无法再增加；接着考虑 2 p − 3 2^p-3 2p−3，此时将第2位变为1，数组变为： [ 0 , 2 , 3 , ⋯ , 2 p − 1 , 2 p − 1 , 2 p − 1 ] [0, 2, 3, ⋯ , 2p−1, 2p−1, 2p−1] [0,2,3,⋯ ,2p−1,2p−1,2p−1]； - 然后接着考虑 3 , 4 , 5 , ⋯ 3,4,5,⋯ 3,4,5,⋯，按照上述最优变换原则，数组最终变换为 [ 0 , 0 , 0 , ⋯ , 2 p − 1 , ⋯ , 2 p − 1 ] [0,0,0,⋯ ,2p−1,⋯ ,2p−1] [0,0,0,⋯ ,2p−1,⋯ ,2p−1]，由于最小乘积不能为 0，所有元素均不能为 0，此时则需要从所有 2 p − 1 2p−1 2p−1 中移除最低位的 1 补充到 0 上，此时数组最终变换为 [ 1 , 1 , 1 , ⋯ , 1 ⏟ 2 p − 1 − 1 , 2 p − 2 , ⋯ , 2 p − 2 ⏟ 2 p − 1 − 1 , 2 p − 1 ] [\underbrace{1,1,1,\cdots,1}_{2^{p-1}-1},\underbrace{2^p-2,\cdots,2^p-2}_{2^{p-1}-1},2^p-1] [2p−1−1 1,1,1,⋯,1,2p−1−1 2p−2,⋯,2p−2,2p−1]，最终的返回值即为 ( 2 p − 1 ) × ( 2 p − 2 ) 2 p − 1 − 1 (2^p-1)\times(2^p-2)^{2^{p-1}-1} (2p−1)×(2p−2)2p−1−1。
以上内容主要参考 官方题解。
快速幂
关于如何快速计算幂指数，可以参考 【面试经典150 | 数学】Pow(x, n)。
实现代码
#define M 1000000007
#define ll long long
class Solution {
public:ll ExpMod(ll a, ll b, ll m){if(b == 0){return 1;}a %= M;ll tmp = ExpMod(a * a % m, b >> 1, m);if(b & 1){tmp = tmp * a % m;}return tmp;}int minNonZeroProduct(int p) {ll p2 = (ll)1 << p;return ExpMod(p2-2, p2/2-1, M) * ((p2-1) % M) % M; }
};
复杂度分析
时间复杂度： O ( p ) O(p) O(p)， p p p 表示给定的数。
空间复杂度： O ( 1 ) O(1) O(1)。
写在最后
如果您发现文章有任何错误或者对文章有任何疑问，欢迎私信博主或者在评论区指出 💬💬💬。
如果大家有更优的时间、空间复杂度的方法，欢迎评论区交流。
最后，感谢您的阅读，如果有所收获的话可以给我点一个 👍 哦。
这篇关于【每日一题】数组元素的最小非零乘积的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
