Tag

【贪心】【快速幂】【数组】【2024-03-20】

---

题目来源

1969. 数组元素的最小非零乘积

---

解题思路

方法一：贪心

前言

我们首先来思考一个简单的问题：假设给定三个整数 $a$，$b$，$c$，满足 $1<=a<b<c$，此时需要将某个数缩小 1，另外一个数增加 1，使得 abc 最小，如恶化选择才能最优？

• 缩小时 优先缩小最小 的元素：当选择 $a$ 缩小 1，此时三者乘积为 $(a-1)bc$；当选择 $b$ 缩小 1，此时三者乘积为 $a(b-1)c$；当选择 $c$ 缩小 1，此时三者乘积为 $ab(c-1)$。比较三者有 $(a-1)bc<a(b-1)c<ab(c-1)$，所以为了使乘积最小，选择缩小最小的元素。
• 增加时 优先增加最大 的元素：此时已经选择了缩小 $a$。当选择 $b$ 增加 1，此时三者乘积为 $(a-1)(b+1)c$；当选择 $c$ 增加 1，此时三者乘积为 $(a-1)b(c+1)$。比较二者有 $(a-1)(b+1)c\le (a-1)b(c+1)$，所以为了使乘积最小，选择增加最大的元素。

位交换的本质

在本题中，将两个数对应的二进制数相同的位进行交换，本质上是将一个数缩小 $2^k$，另一个数增加 $2^k$，其中 k 是交换的第几位（二进制数从低位向高位方向数，从 0 开始数）。可以自行举例子加以理解。

示例分析

根据以上分析，我们可以知道一种贪心思路：进行相同位交换时，优先缩小数组中的自小元素，再增加数组中的最大元素。

设当前数组位 $[1,2,3,...,2^p-2,2^p-1]$，缩小时按照从小到大考虑每个元素：

• 首先考虑缩小 1，此时需要将 1 减少 1，此时从右向左依次考虑最大的元素，由于 $2p-1$ 每一位均为 1 无法再增加；接着考虑 $2^p-2$，此时将最低位变为 1，数组变为：$[0,2,3,\cdots ,2p-3,2p-1,2p-1]$；
• 接着考虑缩小 2，此时需要将 2 减少 2，此时从右向左依次考虑最大的元素，由于 $2p-1$ 每一位均为 1 无法再增加；接着考虑 $2^p-3$，此时将第 2 位变为 1，数组变为：$[0,2,3,\cdots ,2p-1,2p-1,2p-1]$；
• 然后接着考虑 $3,4,5,\cdots$，按照上述最优变换原则，数组最终变换为 $[0,0,0,\cdots ,2p-1,\cdots ,2p-1]$，由于最小乘积不能为 0，所有元素均不能为 0，此时则需要从所有 $2p-1$ 中移除最低位的 1 补充到 0 上，此时数组最终变换为 $[\underset{2^{p-1}-1}{\underbrace{1,1,1,\cdots ,1}},\underset{2^{p-1}-1}{\underbrace{2^p-2,\cdots ,2^p-2}},2^p-1]$，最终的返回值即为 $(2^p-1)\times (2^p-2{)}^{2^{p-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)$，$p$ 表示给定的数。

空间复杂度：$O(1)$。

---

写在最后

如果您发现文章有任何错误或者对文章有任何疑问，欢迎私信博主或者在评论区指出 💬💬💬。

如果大家有更优的时间、空间复杂度的方法，欢迎评论区交流。

最后，感谢您的阅读，如果有所收获的话可以给我点一个 👍 哦。