2023-05-29：给你一个由 n 个正整数组成的数组 nums
你可以对数组的任意元素执行任意次数的两类操作
如果元素是 偶数 ，除以 2
例如，如果数组是 [1,2,3,4]
那么你可以对最后一个元素执行此操作使其变成 [1,2,3,2]
如果元素是 奇数 ，乘上 2
例如，如果数组是 [1,2,3,4] ，那么你可以对第一个元素执行此操作，使其变成 [2,2,3,4]
数组的 偏移量 是数组中任意两个元素之间的 最大差值。
返回数组在执行某些操作之后可以拥有的 最小偏移量。
输入：nums = [4,1,5,20,3]。
输出：3。
答案 2023-05-29：
大体步骤如下：
1.首先定义一个类型为 IntHeap 的结构体，它实现了堆的基本操作，并重写了 Less 方法以实现最大堆。
2.在 minimumDeviation() 函数中，创建一个空的 IntHeap 类型的堆 h，并使用给定的数据填充它。对于堆中的每个元素，如果它是奇数，则将其乘以 2 并插入堆中；否则，将其直接插入堆中。
3.初始化变量 res 为堆中最大元素与最小元素之差。
4.在一个 while 循环中，只要当前解仍可减小且堆中最大元素为偶数，就执行以下操作：
从堆中取出最大值 curMax。
将 curMax 除以 2 并插入堆中。
计算当前解并更新 res。
5.返回变量 res 作为结果。
该算法的时间复杂度为 O(nlogn)，其中 n 是数组的长度。
在最坏情况下，我们需要对所有奇数元素乘以 2，因此数组中的每个元素最多会被操作两次（一次除以 2，一次乘以 2）。这样，我们就需要执行 2n 次操作。由于堆的插入和删除操作都需要 O(logn) 的时间，因此算法的总时间复杂度为 O(nlogn)。
该算法的空间复杂度为 O(n)，其中 n 是数组的长度。我们需要使用一个堆来存储数组的所有元素，因此需要使用 O(n) 的额外空间。
go 完整代码如下：
package main
import ( "container/heap" "fmt" "math")
type IntHeap []int
func minimumDeviation(nums []int) int {
h := IntHeap{} minVal := math.MaxInt32 for i := range nums { if nums[i]&1 == 1 { nums[i] <<= 1 } minVal = min(minVal, nums[i]) heap.Push(&h, nums[i]) }
res := h[0] - minVal for h[0]&1 == 0 { curMax := heap.Pop(&h).(int) minVal = min(minVal, curMax/2) heap.Push(&h, curMax/2) res = min(res, h[0]-minVal) } return res}
func (h IntHeap) Len() int { return len(h) }func (h IntHeap) Less(i, j int) bool { return h[i] > h[j] }func (h IntHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *IntHeap) Push(x interface{}) { *h = append(*h, x.(int))}
func (h *IntHeap) Pop() interface{} { old := *h n := len(old) x := old[n-1] *h = old[0 : n-1] return x}
func min(a, b int) int { if a < b { return a } return b}
func main() { nums := []int{4, 1, 5, 20, 3} fmt.Println(minimumDeviation(nums))}
复制代码
rust 完整代码如下：
use std::cmp::Reverse;use std::collections::BTreeSet;
fn minimum_deviation(nums: Vec<i32>) -> i32 { // 有序表，小 -> 大 组织 // 最大 set.last() let mut set = BTreeSet::new(); for num in nums { set.insert(if num % 2 == 0 { num } else { num * 2 }); }
// 答案 let mut ans = set.iter().next_back().unwrap() - set.iter().next().unwrap(); while ans > 0 && *set.iter().next_back().unwrap() % 2 == 0 { // 最大值 let max = *set.iter().next_back().unwrap(); set.remove(&max); set.insert(max / 2); ans = ans.min(set.iter().next_back().unwrap() - set.iter().next().unwrap()); } ans}
fn main() { let nums = vec![4, 1, 5, 20, 3]; let result = minimum_deviation(nums); println!("{}", result);}
复制代码
c++完整代码如下：
#include <iostream>#include <vector>#include <set>using namespace std;
int minimumDeviation(vector<int>& nums) { // 将奇数转换为偶数 for (int& num : nums) { if (num % 2 == 1) { num *= 2; } }
// 构建有序集合 multiset<int> s(nums.begin(), nums.end());
// 答案 int ans = *s.rbegin() - *s.begin(); while (ans > 0 && *s.rbegin() % 2 == 0) { // 最大值 int max_val = *s.rbegin(); s.erase(--s.end()); s.insert(max_val / 2); ans = min(ans, *s.rbegin() - *s.begin()); } return ans;}
int main() { vector<int> nums = { 4, 1, 5, 20, 3 }; cout << minimumDeviation(nums) << endl; return 0;}
复制代码
c 语言完整代码如下：
#include <stdio.h>#include <stdlib.h>
// 比较两个整数的大小（用于 qsort 排序）int cmp(const void* a, const void* b) { return *(int*)a - *(int*)b;}
// 在有序数组中找到第一个大于等于 key 的元素的下标int lower_bound(int* nums, int size, int key) { int left = 0, right = size, mid; while (left < right) { mid = left + (right - left) / 2; // 防止溢出 if (nums[mid] < key) { left = mid + 1; } else { right = mid; } } return left;}
// 向右移动数组中指定范围内的元素void shift_right(int* nums, int start, int end) { for (int i = end; i >= start; --i) { nums[i + 1] = nums[i]; }}
int minimumDeviation(int* nums, int numsSize) { // 将奇数转换为偶数 for (int i = 0; i < numsSize; ++i) { if (nums[i] % 2 == 1) { nums[i] *= 2; } }
// 构建有序集合 int* s = malloc(numsSize * sizeof(int)); int size = 0; for (int i = 0; i < numsSize; ++i) { int num = nums[i]; if (num % 2 == 0) { s[size++] = num; } else { s[size++] = num * 2; } } qsort(s, size, sizeof(int), cmp);
// 答案 int ans = s[size - 1] - s[0]; while (ans > 0 && s[size - 1] % 2 == 0) { // 最大值 int max_val = s[--size]; s[size] = max_val / 2; int insert_index = lower_bound(s, size, s[size]); shift_right(s, insert_index, size - 1); s[insert_index] = max_val / 2; ans = min(ans, s[size - 1] - s[0]); } free(s); return ans;}
int main() { int nums[] = { 4, 1, 5, 20, 3 }; int result = minimumDeviation(nums, 5); printf("%d\n", result); return 0;}
复制代码
![2023-05-29：给你一个由 n 个正整数组成的数组 nums 你可以对数组的任意元素执行任意次数的两类操作 如果元素是 偶数 ，除以 2 例如，如果数组是 [1,2,3,4] 那么你可以对最后一_golang_福大大架构师每日一题_InfoQ写作社区](https://static001.infoq.cn/static/infoq/img/logo-121-75.yuij86g.png){kind=logo}
评论