最小化数组中的偏差

问题陈述

给你一个包含 n 个正整数的数组 nums。

你可以对数组中的任何元素执行以下两种操作任意次数

如果元素是偶数，则将其除以 2。

例如，如果数组是 [1,2,3,4]，则可以对最后一个元素执行此操作，数组将变为 [1,2,3,2]。

如果元素是奇数，则将其乘以 2。

例如，如果数组是 [1,2,3,4]，则可以对第一个元素执行此操作，数组将变为 [2,2,3,4]。

数组的偏差定义为数组中任意两个元素之间的最大差值。

返回数组执行一些操作后可以达到的最小偏差。

Java 实现

Java 使用 TreeSet 的方法

输出

代码解释

• 该代码定义了一个 MinimumDeviation 类，其中包含一个 minimumDeviation 方法，用于查找数组元素之间的最小偏差。它使用 TreeSet 来存储将奇数翻倍后的元素。该算法迭代计算最大值和最小值之间的差值，并更新最小偏差。如果最大元素是偶数，则将其除以 2 并继续该过程。
• 迭代停止的条件是当最大元素变为奇数时。该代码利用 TreeSet 来维护排序顺序，从而方便地访问最小值和最大值。

时间复杂度

• 时间复杂度为 O(n log n)，其中 n 是输入数组的元素数量。此复杂度源于涉及 TreeSet 的操作。

空间复杂度

• 空间复杂度为 O(n)，表示 TreeSet 用于存储修改后数组的元素所使用的空间，确保唯一性并方便高效地检索最小值和最大值。

Java 使用优先队列的方法

输出

代码解释

• 该代码定义了一个 MinimumDeviation 类，其中包含一个 minimumDeviation 方法，用于查找数组元素之间的最小偏差。它利用反向排序的 PriorityQueue 来有效地检索最大元素。该算法将奇数翻倍，将它们添加到 PriorityQueue 中，并跟踪最小值。
• 然后，它迭代计算最大值和最小值之间的偏差，并更新最小偏差。如果最大值为偶数，则将其除以 2 并继续该过程。迭代停止的条件是当最大元素变为奇数时。

时间复杂度

• 时间复杂度为 O(n log n)，其中 n 是输入数组的元素数量。这源于对 PriorityQueue 的操作。

空间复杂度

• 空间复杂度为 O(n)，表示 PriorityQueue 用于存储修改后数组元素所使用的空间。