建设网站文章哪里下载,wordpress调用文章,广告制作费和广告服务费区别,营销企业网站建设数组里面有n个正整数#xff0c;里面的数字可以无限次进行如下操作#xff1a; 1.偶数可以除以2 2.奇数可以乘以2 数组中任意两元素差的最大值称为偏差。 把数组中的元素进行上面2种操作#xff0c;使偏差最小。
思路#xff1a;
数组中现有2种数字#xff0c;一种是奇数… 数组里面有n个正整数里面的数字可以无限次进行如下操作 1.偶数可以除以2 2.奇数可以乘以2 数组中任意两元素差的最大值称为偏差。 把数组中的元素进行上面2种操作使偏差最小。
思路
数组中现有2种数字一种是奇数一种是偶数 我们来分析下这2种数字能操作多少次。
奇数可以 ✖2✖2之后必然为偶数然后就不能再乘了 下一步只能➗2但是➗2就会回到这个奇数本身。如果继续操作就会无限循环。 所以奇数✖2后即可停止。
偶数可以➗2➗2之后可能是奇数也可能是偶数 如果是偶数可以继续➗2 如果是奇数只能✖2那么就会回到这个偶数本身或者是中间过程的偶数。 所以在偶数➗2得到奇数时就不应该再继续操作了因为继续操作又会回到原点或中间点。
分析完之后观察数组直觉上应该如下解决此问题
数组排序选最大的数如果最大的是奇数只能✖2数字会继续变大拉大偏差因此没有操作性 如果最大的数是偶数可以➗2把它变小缩小偏差更新最小偏差把➗2后的数字放回数组。
然后取最小的数如果是奇数把它✖2缩小偏差更新最小偏差✖2后放回数组。
现在假设数字放回数组之后都会自动排序
那么可以重复上面的步骤直到最大的数字是奇数最小的数字是偶数这是终止条件。 因为继续操作下去最大的会变大最小的会变小又拉大了偏差
但是同时操作奇数和偶数会有如下麻烦 比如偶数➗2得到奇数放回数组那么下次想把最小的奇数✖2时这个奇数是数组原有的奇数还是偶数➗2后得到的奇数呢 如果偶数➗2得到的奇数比原数组的奇数小那么原数组的奇数可能就没有操作的机会。
所以要降低维度只操作奇数或偶数。 如果只操作奇数那么偶数就没有操作的机会 如果只操作偶数只要奇数一开始的时候✖2变为偶数那么它就可以变回原奇数。
所以在开始的时候先把所有奇数✖2整个数组都变为偶数就可以达到只操作偶数的目的。 偶数➗2一旦变为奇数即停止。 每次➗2后要放回数组同时数组要一直保持排序的状态这样每次都能取出数组的最小值和最大值。 或者手动记录最小值每次能取出最大值也可以用优先队列。
怎么能让数组一直保持排序的状态呢用红黑树的数据结构也就是TreeSet.
每操作一次记录一次偏差的最小值这个最小值可能是在中间过程中产生的。 public int minimumDeviation(int[] nums) {int n nums.length;TreeSetInteger ts new TreeSet();for(int num : nums) {if(num % 2 ! 0) num * 2;ts.add(num);}int res ts.last()-ts.first();while(ts.last() % 2 0) {ts.add(ts.pollLast() / 2);res Math.min(res, ts.last()-ts.first());}return res;}
