本文主要是介绍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;}
};这篇关于leetcode 1969.数组元素的最小非零乘积的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
