資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究最小化陣列中相鄰元素之間的最大差值
在這個問題中，我們將透過從陣列中移除任何 M 個元素來最小化相鄰元素之間的最大差值。
解決該問題的樸素方法是從陣列中選擇總共 N − M 個數組元素，並檢查哪個集合包含最小或最大相鄰差值。最佳化的解決方案使用佇列資料結構來解決該問題。
問題陳述：我們給定一個按升序排序的數字陣列。我們也給定了 M。我們需要從陣列中移除 M 個元素，以便最小化相鄰陣列元素之間的最大差值。
示例
輸入
nums = {5, 9, 12, 13, 14, 19}, M = 3
輸出
1
解釋：我們可以從陣列中移除 5、9 和 19。因此，相鄰陣列元素之間最大差值的最小值為 1。
輸入
nums = {8, 9, 12, 13, 17}, M = 2
輸出
3
解釋：我們可以移除 8 和 17 以最小化最大相鄰差值。
輸入
nums = {8, 9, 10, 11, 12, 13}, K = 1
輸出
1
解釋：我們可以移除任何 3 個元素，因為所有元素之間的相鄰差值都相同。
方法 1
在這裡，我們將使用蠻力方法來解決問題。從陣列中，我們可以建立 2N 個集合。之後，我們檢查每個 N − K 元素集合的最大相鄰差值，並將它們中的最小值作為答案。
演算法
步驟 1 - 使用最大整數值初始化 'min_diff' 值。
步驟 2 - 使用 for 迴圈進行 2N 次迭代。
步驟 3 - 接下來，使用 __builtin_popcount() 方法查詢 'p'（當前索引）中設定位的數量，並將其儲存在 'cnt' 方法中。
步驟 4 - 如果 'cnt' 等於 N − K，請執行以下步驟。
步驟 4.1 - 初始化 'tmp' 列表以儲存陣列元素。
步驟 4.2 - 開始遍歷陣列。如果當前位在索引 'p' 中是設定位，則將元素插入到 'tmp' 列表中。
步驟 4.3 - 使用最小整數值初始化 max_diff。
步驟 4.4 - 遍歷陣列元素並找到最大相鄰差值。
步驟 4.5 - 之後，如果 min_diff 大於 max_diff，則更新 min_diff。
步驟 5 - 返回 min_diff 值。
示例
#include <bits/stdc++.h>
using namespace std;
int minimumDiff(vector<int> nums, int len, int M) {
// Minimum difference
int min_diff = INT_MAX;
// Traverse for 2^N subsets
for (int p = 0; p < (1 << len); p++) {
// Number of array elements to be considered in the given set. It gives the number of 1 in the binary string
int cnt = __builtin_popcount(p);
// When len - M elements are left in the set
if (cnt == len - M) {
// temporary array
vector<int> tmp;
for (int q = 0; q < len; q++) {
if ((p & (1 << q)) != 0)
tmp.push_back(nums[q]);
}
// To store the maximum difference of adjacent elements
int max_diff = INT_MIN;
for (int q = 0; q < tmp.size() - 1; q++) {
max_diff = max(max_diff, tmp[q + 1] - tmp[q]);
}
min_diff = min(min_diff, max_diff);
}
}
return min_diff;
}
int main() {
int M = 3;
vector<int> nums = {5, 9, 12, 13, 14, 19};
int len = nums.size();
cout << "The minimum of maximum difference between adjacent elements is " << minimumDiff(nums, len, M);
return 0;
}
輸出
The minimum of maximum difference between adjacent elements is 1
時間複雜度 - O(N*2N)，其中 O(N) 用於遍歷陣列，O(2N) 用於檢查陣列的每個子集。
空間複雜度 - O(N − M) 用於儲存陣列元素。
方法 2
我們可以觀察到，從陣列中間移除陣列元素總是會增加陣列元素之間的差值，因為陣列按升序排序。因此，我們總是需要從陣列的兩端移除陣列元素。
例如，陣列為 [2, 5, 7, 9, 10]。如果我們移除 9，它會增加 7 和 10 之間的差值。因此，從兩端移除陣列元素是一個好主意。
為了解決這個問題，我們將陣列中相鄰元素的差值儲存起來。之後，我們將遍歷大小為 N − K 的每個子陣列，並使用滑動視窗技術獲取所有子陣列中最大相鄰差值的最小值。
演算法
步驟 1 - 遍歷陣列並將下一個元素和當前元素之間的差值儲存在 nums_diff[p] 中。
步驟 2 - 執行 findMinimum() 函式以查詢每個子陣列中的最小差值。
步驟 3 - 在 findMinimum() 函式中，建立一個大小為 k 的雙端佇列以儲存陣列元素的索引。
步驟 4 - 使用迴圈處理第一個視窗。如果佇列不為空，並且佇列最後一個索引處的元素大於當前元素，則從佇列中移除該元素。此外，使用 while 迴圈移除所有大於當前元素的元素。
步驟 5 - 將當前元素插入到佇列中。
步驟 6 - 現在，我們需要處理其他視窗。因此，使用最大整數值初始化 min_diff 並開始遍歷其他視窗。
步驟 7 - 如果 ind_que.front() 索引處的元素小於 min_diff，則更新 min_diff 變數的值。
步驟 8 - 使用迴圈，從佇列中移除前一個視窗的索引。
步驟 9 - 移除小於當前元素的元素的索引，並將當前元素插入到佇列中。
步驟 10 - 處理最後一個視窗的 min_diff 值並從函式中返回它。
示例
#include <bits/stdc++.h>
using namespace std;
int findMinium(vector<int> arr, int n, int k) {
// Deque to store array indexes
deque<int> ind_que(k);
int p;
// Handle the first window
for (p = 0; p < k; ++p) {
// Remove smaller elements from the back of queue
while ((!ind_que.empty()) && arr[p] >= arr[ind_que.back()])
ind_que.pop_back(); // Remove last element
// Add curent index to queue
ind_que.push_back(p);
}
int min_diff = INT_MAX;
// Handle other windows
for (; p < n; ++p) {
// The first element is largest in deque
min_diff = min(min_diff, arr[ind_que.front()]);
// Update the current window
while ((!ind_que.empty()) && ind_que.front() <= p - k)
ind_que.pop_front();
// Remove smaller elements than current element
while ((!ind_que.empty()) && arr[p] >= arr[ind_que.back()])
ind_que.pop_back();
// Push current element
ind_que.push_back(p);
}
// Handle the last window
min_diff = min(min_diff, arr[ind_que.front()]);
return min_diff;
}
int minimumDiff(vector<int> nums, int len, int M) {
// Difference array
vector<int> nums_diff(len - 1);
for (int p = 0; p < len - 1; p++) {
nums_diff[p] = nums[p + 1] - nums[p];
}
return findMinium(nums_diff, len - 1, len - M - 1);
}
int main() {
int M = 2;
vector<int> nums = {8, 9, 12, 13, 17};
int len = nums.size();
cout << "The minimum of maximum difference between adjacent elements is " << minimumDiff(nums, len, M);
return 0;
}
輸出
The minimum of maximum difference between adjacent elements is 3
時間複雜度 - O(N)
空間複雜度 - O(N) 用於將差值儲存到佇列中。
我們使用雙端佇列資料結構，因為我們可以在雙端佇列的兩端執行插入和刪除操作。程式設計師可以嘗試使用不同的資料結構（如陣列）來解決此問題。
484 次瀏覽
