通过给定操作求出数组中最大值与最小值之间的最小差值
在本题中，我们将求出将任意数组元素乘以或除以 K 后，数组中最小元素与最大元素之间的最小差值。
解决这个问题的简单方法是，如果数组中的每个元素可被 K 整除，则将其除以 K;如果每个元素可被 K 整除，则将其乘以 K;然后追踪数组中的最小元素和最大元素。
问题描述
给定一个包含整数值和正整数 K 的数组 nums[]。我们可以将 nums[] 数组中的任意数字乘以 K，或者如果可被 K 整除，则将其除以 K。给定的任务是，在对数组中的任意元素执行给定操作后，找出数组中最大值与最小值之间的最小差值。
示例
输入
nums = {1, 6000, 11099, 8000}; k = 12000;
输出
6000
解释
初始时，数组的最大值和最小值分别为 11099 和 1。将 1 乘以 12000 后，最大值为 12000，最小值为 6000。因此，最小差值为 6000。
输入
nums = {3, 1, 4, 10, 2, 7, 5}; k = 10;
输出
6
解释
如果将 10 除以 10，结果为 1。因此，最小值为 1，数组的最大值为 7。最大值和最小值之间的最小差为 6。
方法
在此方法中，我们将对数组元素进行 K 次乘除后存储所有可能的值。之后，我们将对值进行排序并遍历它们。当每个索引都有 K 个值为 1 的值时，我们将找到最小值和最大值，并跟踪这些值之间的最小差值。
算法
步骤 1 - 定义用于存储整数对的列表。该对的第一个元素将包含原始或更新后的数组元素，第二个对将包含其索引。
步骤 2 - 遍历数组元素。在循环中，将 {nums[p], p}、{nums[p] * k, p} 和 {nums[p] / k, p} 对插入到列表中。其中，nums[p] 是数组中索引 p 处的元素。
步骤 3- 使用 sort() 方法对列表进行排序。
步骤 4- 定义名为 map 的 numMap 来跟踪已访问的元素。此外，定义 minDiff 来存储最小差值，定义 minValInd 和 maxValInd 来存储最小和最大元素的索引。
步骤 5- 现在，遍历 'que' 列表。
步骤 5.1- 从 'que' 列表中取出第一对。将对的第一个元素存储在 temp 中，将第二个元素存储在 p 中。同时，从 'que' 列表中删除第一个对。
步骤 5.2 − 如果 minValInd 为 -1 或 numMap[minValInd] 大于 temp，则用 p 初始化 minValInd。此外，如果 maxValInd 为 -1 或 numMap[maxValInd] 小于 temp，则用 p 初始化 maxValInd。
步骤 5.3 − 接下来，用 temp 值更新 numMap[p]。
步骤 5.4 − 现在，遍历 map 并找到 map 中存储的最小值和最大值。
步骤 5.5 − 如果 maxValInd 等于 p，且 numMap[maxValInd] 不等于 maxVal，则从 map 中找出最大值并根据其索引更新 maxValInd。
"que"列表中的每个索引都有 3 个值。因此，之前的最大值可能会被更新，我们需要找到另一个元素。
步骤 5.6 - 按照上一步中更新 maxValInd 值的方式调整 minValInd 值。
步骤 5.7 - 如果映射的大小等于数组大小，则取映射最小值与最大值之间的差值，如果差值大于结果值，则更新 'minDiff' 值。
此处，映射的大小等于数组的大小意味着映射包含数组每个索引中的元素。
示例
#include <bits/stdc++.h>
using namespace std;
int findMinMax(vector<int> nums, int k) {
vector<pair<int, int>> que;
// 将所有可能的值插入队列
for (int p = 0; p < nums.size(); p++) {
// 原始值
que.push_back({nums[p], p});
// 乘以 K
que.push_back({nums[p] * k, p});
// 如果可整除，则除以 K
if (nums[p] % k == 0) {
que.push_back({nums[p] / k, p});
}
}
// 对队列进行排序
sort(que.begin(), que.end());
int minDiff = INT_MAX;
// 跟踪已访问的元素
map<int, int> numMap;
// 跟踪最小值和最大值的索引
int minValInd = -1;
int maxValInd = -1;
// BFS 算法
while (!que.empty()) {
int temp = que[0].first;
int p = que[0].second;
que.erase(que.begin());
// 初始化
if (minValInd == -1 || numMap[minValInd] > temp) {
minValInd = p;
}
if (maxValInd == -1 || numMap[maxValInd] < temp) {
maxValInd = p;
}
numMap[p] = temp;
// 查找最小和最大映射值
int maxVal = INT_MIN;
int minVal = INT_MAX;
// Traverse map
for (auto &ele : numMap) {
maxVal = max(maxVal, ele.second);
minVal = min(minVal, ele.first);
}
// 在 numMap 中添加新值后调整最大值和最小值。
// 两个元素的索引可以相同，因为我们在乘法和除法之后也会添加元素
if (maxValInd == p && numMap[maxValInd] != maxVal) {
for (auto &ele : numMap) {
if (numMap[maxValInd] < ele.second) {
maxValInd = ele.first;
}
}
}
if (minValInd == p && numMap[minValInd] != minVal) {
for (auto &ele : numMap) {
if (numMap[minValInd] > ele.second) {
minValInd = ele.first;
}
}
}
// 当 map 包含所有索引时
if (numMap.size() == nums.size()) {
minDiff = min(minDiff, numMap[maxValInd] - numMap[minValInd]);
}
}
return minDiff;
}
int main() {
vector<int> nums = {1, 6000, 11099, 8000};
int k = 12000;
cout << "更新后最小元素与最大元素之差为 " << findMinMax(nums, k);
return 0;
}
输出
更新后最小元素与最大元素之差为 - 6000
时间复杂度− O(N*logN) 对数组进行排序。
空间复杂度 − O(N) 将元素存储到 'que' 列表和 map 中。
结论
这里我们使用了 'que' 列表并对其进行了排序。但是，我们也可以使用优先级队列来存储元素，从而提高代码性能。
