C++ 最小差异的最大值和最小值之间的数组的给定操作

在这个问题中，我们将找到最小差异，在将数组元素与K相乘或相除之后，最小和最大数组元素之间的差异。

解决该问题的简单方法是如果可除，将数组的每个元素除以K，将数组的每个元素乘以K，并跟踪数组的最小和最大元素。

问题陈述

我们已经给出包含整数值和正整数K的数组nums[]。如果可被K整除，我们可以用K乘以nums[]数组的任意数量或将其除以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时，我们将找到最小值和最大值，并跟踪这些值的最小差。

算法

• 第一步 - 定义一个列表来存储整数对。对的第一个元素将包含原始或更新后的数组元素，第二个对将包含索引。

• 第二步 - 遍历数组元素。在循环中，将{nums[p]，p}，{nums[p] * k，p}和{nums[p]/k，p}对插入到列表中。这里，nums[p]是数组中索引p处的元素。

• 第三步 - 使用sort()方法对列表进行排序。

• 第四步 - 定义名为map的numMap来跟踪访问过的元素。还要定义minDiff来存储最小差异，minValInd和maxValInd来存储最小和最大元素的索引。

• 第五步 - 现在，遍历’que’列表。

• 第5.1步 - 从’que’列表中取出第一对。将对的第一个元素存储在temp中，第二个元素存储在p中。还要从’que’列表中删除第一对。

• 第5.2步 - 如果minValInd为-1或numMap[minValInd]大于temp，则将minValInd初始化为p。此外，如果maxValInd为-1或numMap[maxValInd]小于temp，则将maxValInd初始化为p。

• 第5.3步 - 接下来，使用temp值更新numMap[p]。

• 第5.4步 - 现在，遍历map并找到存储在map中的最小值和最大值。

• 第5.5步 - 如果maxValInd等于p，并且numMap[maxValInd]不等于maxVal，则从map中找到最大值并根据其索引更新maxValInd。

在’que’列表中每个索引有3个值。因此，先前的最大值可能被更新，我们需要找到另一个元素。

• 第5.6步 - 调整minValInd的值，因为在上一步中更新了maxValInd的值。

• 第5.7步 - 如果map的大小等于数组的大小，则取map的最小值和最大值之间的差值，并在结果值大于minDiff时更新’minDiff’值。

这里，map的大小等于数组的大小意味着map包含数组每个索引的元素。

例子

#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’ 列表并对其进行了排序。然而，我们也可以使用优先队列来存储元素并提高代码性能。