資料結構
網路
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 次檢視
