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

在讲本题之前，我们首先科普一点数学的推导：

首先就是，a,b,c三个不为0的正整数，a<b<c，他们的乘积就是abc。

问：当我们缩小一个数的时候，缩小哪个数才能让它们三个的乘积最小呢？我们可以从最小的和最大的入手，首先我们缩小最小的a，假如我们缩小1，那么乘积就变成了：(a-1)bc=abc-bc。接下来我们看缩小最大的那个数：ab(c-1)=abc-ab。由于ab<bc，所以我们看到，如果我们缩小最小的那个数，他们的乘积就会缩小；

再来，还是这三个数abc，不过我们运用上面缩小了最小数的乘积(a-1)bc，我们在这个乘积的基础上再对于一个数增加，怎样才能使增加一个数时候的乘积最小呢？这个时候我们看b和c，因为a我们已经操作完了，所以我们的目光当然要转向这两个数。当我们增大b的时候，假如也是增加1吧，我们的乘积就变成了（a-1)(b+1)c=(a-1)bc+(a-1)c.如果我们增加c，那么(a-1)b(c+1)=(a-1)bc+(a-1)b.这个时候我们看增加的部分，(a-1)c>(a-1)b，这样比较下来我们知道，在我们缩小了最小值的基础上，我们对于最大值的增大，才会使这个乘积最小化。

再来看我们的题目，这里其实这里的二进制的相同位数调换其实就是对于一个数增加pow(2,p）或者减少pow(2,p），也就上面的数学问题一致化了。这个时候，根据上面得到的结论：在缩小乘积时，缩小时我们需要缩小最小的那个数，增大时我们需要增大最大的那个数。

OK，这样我们来看题目：既然说以上面的结论作为前提我们就需要从左向右找最小值，从右到左找最大值。

首先看1和pow(2,p）-1.，我们可以清楚的知道，这个时候位数是不会交换的，因为最大数的全部位数都是1，所以没办法对于0的位数进行交换，所以我们看第二大的数：也就是pow(2,p）-2这个时候，就有0的存在了，交换之后，1变成了0，另一个数就变成了pow(2,p)-1。是不是就符合前面的结论了呢？是的，也就是增加最大的数，减小最小的数。就这样依次类推下去.....

我们最终会得到0,0,0,......,pow(2,p)-1,pow(2,p)-1。由于我们的乘积并不能为0，这个时候我们就需要把这些大数上的最低位的1与0上的最低位进行交换，就变成了1,1,1,.....,pow(2,p)-2,pow(2,p)-2，pow(2,p)-1的序列，其中，1有pow(2,p-1)-1个，同时pow(2,p)-2也有pow(2,p-1)-1个（这里可以自己算一下，也就是总共有pow(2,p)-1个数，我们去掉pow(2,p)-1本身，然后再除以2，就得到了1和pow(2,p)-2的个数，因为它们之间是成对的交换的，所以需要除以2）

有人可能发现了，这里计算量那么大，是不是需要有一点数学的手段进行操作呢？是的，这里可以用快速幂进行计算。所以我们自己手写一个，然后用上就行了，最后的乘积大家根据刚刚的序列也知道了，就是（pow(2,p)-1)*(pow(pow(2,p)-2,pow(2,p-1)-1).

上代码：

class Solution {
public:
    long long fast(long long x,long long n, long long mod){
        long long res=1;
        for(;n!=0;n>>=1){
            if(n&1){
                res=res*x%mod;
            }
            x=x*x%mod;
        }
        return res;
    }
    int minNonZeroProduct(int p) {
        if(p==1)
        return 1;
        long long mod=1e9+7;
        long long x=fast(2,p,mod)-1;
        long long y=(long long)1<<(p-1);
        return fast(x-1,y-1,mod)*x%mod;
    }
};

原文地址：https://blog.csdn.net/m0_73917165/article/details/136891431

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！