数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究给定操作后数组最大值和最小值的最小差值
在这个问题中，我们将找到在将任何数组元素乘以或除以 K 后，数组元素的最小值和最大值之间的最小差值。
解决该问题的简单方法是，如果数组的每个元素都可以被 K 整除，则将其除以 K，将每个元素乘以 K，并跟踪数组的最小值和最大值。
问题陈述
我们给定一个包含整数值的数组 nums[] 和一个正整数 K。我们可以将 nums[] 数组中的任意数量的数字乘以 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 - 定义名为 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 - 现在，遍历映射并找到存储在映射中的最小值和最大值。
步骤 5.5 - 如果 maxValInd 等于 p，并且 numMap[maxValInd] 不等于 maxVal，则从映射中查找最大值并根据其索引更新 maxValInd。
在“que”列表中，每个索引都有 3 个值。因此，有可能先前的最大值被更新，我们需要找到另一个元素。
步骤 5.6 - 调整 minValInd 值，因为我们在上一步中更新了 maxValInd 值。
步骤 5.7 - 如果映射的大小等于数组的大小，则取映射的最小值和最大值之间的差值，如果该差值大于结果值，则更新“minDiff”值。
这里，映射的大小等于数组的大小意味着映射包含数组每个索引的元素。
示例
#include <bits/stdc++.h>
using namespace std;
int findMinMax(vector<int> nums, int k) {
vector<pair<int, int>> que;
// Insert all possible values in the queue
for (int p = 0; p < nums.size(); p++) {
// Original value
que.push_back({nums[p], p});
// Multiply by K
que.push_back({nums[p] * k, p});
// Divide by K if it is divisible
if (nums[p] % k == 0) {
que.push_back({nums[p] / k, p});
}
}
// Sort the queue
sort(que.begin(), que.end());
int minDiff = INT_MAX;
// To track visited elements
map<int, int> numMap;
// To track the Index of minimum and maximum value
int minValInd = -1;
int maxValInd = -1;
// BFS algorithm
while (!que.empty()) {
int temp = que[0].first;
int p = que[0].second;
que.erase(que.begin());
// Initialization
if (minValInd == -1 || numMap[minValInd] > temp) {
minValInd = p;
}
if (maxValInd == -1 || numMap[maxValInd] < temp) {
maxValInd = p;
}
numMap[p] = temp;
// Finding minimum and maximum map value
int maxVal = INT_MIN;
int minVal = INT_MAX;
// Traverse map
for (auto &ele : numMap) {
maxVal = max(maxVal, ele.second);
minVal = min(minVal, ele.first);
}
// adjust max and min value after adding new value in numMap.
// Index can be same for two elements as we add elements after multiplying and dividing also
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;
}
}
}
// When map contains all indexes
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 << "The difference between minimum and maximum element after updating is " << findMinMax(nums, k);
return 0;
}
输出
The difference between minimum and maximum element after updating is - 6000
时间复杂度 - O(N*logN) 用于对数组进行排序。
空间复杂度 - O(N) 用于将元素存储到“que”列表和映射中。
结论
这里，我们使用了“que”列表并对其进行了排序。但是，我们也可以使用优先队列来存储元素并提高代码性能。
182 次查看
