2023-05-29:给你一个由 n 个正整数组成的数组 nums 你可以对数组的任意元
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;
}
本作品采用《CC 协议》,转载必须注明作者和本文链接
推荐文章: