[leetcode] 1675. 数组的最小偏移量 | 思维贪心 | 大疆笔试题

简介: [leetcode] 1675. 数组的最小偏移量 | 思维贪心 | 大疆笔试题

题目链接

来源:力扣(LeetCode)

链接:https://leetcode.cn/problems/minimize-deviation-in-array

著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

示例 1:


输入:nums = [1,2,3,4]

输出:1

解释:你可以将数组转换为 [1,2,3,2],然后转换成 [2,2,3,2],偏移量是 3 - 2 = 1

示例 2:

输入:nums = [4,1,5,20,3]

输出:3

解释:两次操作后,你可以将数组转换为 [4,2,5,5,3],偏移量是 5 - 2 = 3

示例 3:


输入:nums = [2,10,8]

输出:3


提示:

n == nums.length

2 <= n <= 5 * 104

1 <= nums[i] <= 109


思路:可以将偶数 / 2,奇数 * 2。但是这样会导致还会出现奇数和偶数同时出现在数列中,所以我们可以将所有的奇数 * 2变成偶数,偶数不变(同时统计最小值),这样一来数列中所有数都是偶数,而由*2得来的偶数可以通过/2得到


当数列中的最大值一直是偶数的时候,为了能够缩小答案,我们贪心的将这个数 / 2之后(可能为奇数可能为偶数)放到数列中,并且刚更新最小值,并统计答案(这就得到了当前这个数的贡献),答案是当前数列的最大的元素减去当前更新后的最小值,当最大的元素为奇数的时候,无法改变(奇数 * 2反而会扩大答案);在这个时候,我们就要开始考虑将最小值变大来缩小和最大值的差距,最小值能够扩大则必定为奇数(只有奇数才能够 * 2),可是在我们处理之后,将所有的值变成了偶数,那么这个奇数一定是由前面的偶数 / 2得来的,那么说这个数的贡献是已经算过了的,所以说可以直接将结果返回啦


ac_code:

class Solution {
public:
    int minimumDeviation(vector<int>& nums) {
        priority_queue<int> q;
        int mini = 0x3f3f3f3f;
        for(int &t:nums) {
            if(t & 1) t <<= 1;
            q.push(t);
            mini = min(mini, t);
        }
        int ans = 0x3f3f3f3f;// q.top() - mini;
        while(q.size() && q.top() % 2 == 0) {
            int tp = q.top();
            tp >>= 1;
            q.pop(),q.push(tp);
            mini = min(mini, tp);
            ans = min(ans, q.top() - mini);
        }
        return ans;
    }
};
目录
打赏
0
0
0
0
5
分享
相关文章
|
4月前
|
Leetcode第53题(最大子数组和)
这篇文章介绍了LeetCode第53题“最大子数组和”的动态规划解法,提供了详细的状态转移方程和C++代码实现,并讨论了其他算法如贪心、分治、改进动态规划和分块累计法。
91 0
|
4月前
|
Leetcode第三十三题(搜索旋转排序数组)
这篇文章介绍了解决LeetCode第33题“搜索旋转排序数组”的方法,该问题要求在旋转过的升序数组中找到给定目标值的索引,如果存在则返回索引,否则返回-1,文章提供了一个时间复杂度为O(logn)的二分搜索算法实现。
39 0
Leetcode第三十三题(搜索旋转排序数组)
|
4月前
|
C++
【LeetCode 12】349.两个数组的交集
【LeetCode 12】349.两个数组的交集
31 0
|
4月前
【LeetCode-每日一题】 删除排序数组中的重复项
【LeetCode-每日一题】 删除排序数组中的重复项
35 4
|
4月前
|
Leetcode 初级算法 --- 数组篇
Leetcode 初级算法 --- 数组篇
58 0
LeetCode第81题搜索旋转排序数组 II
文章讲解了LeetCode第81题"搜索旋转排序数组 II"的解法,通过二分查找算法并加入去重逻辑来解决在旋转且含有重复元素的数组中搜索特定值的问题。
LeetCode第81题搜索旋转排序数组 II
LeetCode第53题最大子数组和
LeetCode第53题"最大子数组和"的解题方法,利用动态规划思想,通过一次遍历数组,维护到当前元素为止的最大子数组和,有效避免了复杂度更高的暴力解法。
LeetCode第53题最大子数组和
LeetCode第34题在排序数组中查找元素的第一个和最后一个位置
这篇文章介绍了LeetCode第34题"在排序数组中查找元素的第一个和最后一个位置"的解题方法,通过使用双指针法从数组两端向中间同时查找目标值,有效地找到了目标值的首次和最后一次出现的索引位置。
LeetCode第34题在排序数组中查找元素的第一个和最后一个位置
LeetCode第33题搜索旋转排序数组
这篇文章介绍了LeetCode第33题"搜索旋转排序数组"的解题方法,通过使用二分查找法并根据数组的有序性质调整搜索范围,实现了时间复杂度为O(log n)的高效搜索算法。
LeetCode第33题搜索旋转排序数组
LeetCode------找到所有数组中消失的数字(6)【数组】
这篇文章介绍了LeetCode上的"找到所有数组中消失的数字"问题,提供了一种解法,通过两次遍历来找出所有未在数组中出现的数字:第一次遍历将数组中的每个数字对应位置的值增加数组长度,第二次遍历找出所有未被增加的数字,即缺失的数字。
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等