資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究使陣列遞減所需的最小減法運算次數
在本文中，我們將透過對陣列進行一些減法運算來對陣列進行降序排序。
問題陳述
給定一個包含一系列 n 個數字的陣列，從 array[0]、array[1]、……、array[ n-1 ]。
我們還給定一個整數 nums。我們的任務是透過在每次操作中從陣列元素中減去 nums 來生成一個遞減陣列。我們需要返回為了使陣列按降序排列而所需的此類操作的最小可能數量。
讓我們用一個例子來理解這個問題 -
Input: n = 5, nums = 2, array[] = {5, 8, 6, 9, 10}
Output: 4
解釋
步驟 1 - 從原始陣列 [5, 8, 6, 9, 10] 開始。
步驟 2 - 由於 array[1] > array[0] (8 > 5)，我們兩次從 array[1] 中減去 nums 以使其小於或等於 array[0]。更新後的陣列變為 [5, 4, 6, 9, 10]。
步驟 3 - 現在，array[2] > array[1] (6 > 4)，因此我們兩次從 array[2] 中減去 nums 以使其小於或等於 array[1]。更新後的陣列變為 [5, 4, 2, 9, 10]。
步驟 4 - 接下來，array[3] > array[2] (9 > 2)，因此我們四次從 array[3] 中減去 nums 以使其小於或等於 array[2]。更新後的陣列變為 [5, 4, 2, -7, 10]。
步驟 5 - 最後，array[4] > array[3] (10 > -7)，因此我們五次從 array[4] 中減去 nums 以使其小於或等於 array[3]。更新後的陣列變為 [5, 4, 2, -7, -15]。
方法
現在，讓我們討論一下這個問題的解決方案方法 -
為了使陣列遞減，我們必須在 0 到 n 之間的任何迭代器中都有 array[iterator] <= array[iterator+1]，因此每當我們遇到相鄰數字使得 array[iterator] > array[iterator+1] 時，我們都必須對 array[iteratot+1] 執行減法運算。
遍歷從索引 1 到 n-1 的陣列的每個元素。這意味著我們從第二個元素開始迭代陣列。
檢查 array[ iterator] 是否大於 array[ iterator-1]。如果此條件為真，則表示當前元素在大小上超過了前一個元素，我們需要使其更小。
計算使 array[ iterator] 小於或等於 array[ iterator-1] 所需的減法次數。使用的公式為 -
Operations_needed = (array[ iterator] - array[iterator-1]) / nums
這計算了我們需要從 array[ iterator] 中減去 K 多少次才能達到小於或等於 array[ iterator-1] 的值。
檢查將 (array[ iterator ] − array[ iterator-1]) 除以 nums 時是否存在餘數。如果餘數為 0，則將 1 新增到 Operations_needed 以確保更新後的 array[ iterator] 小於 array[ iterator-1]。此步驟確保我們進行必要的調整以確保 array[ iterator] 小於或等於 array[ iterator-1]。
透過從 array[iterator] 中減去 (nums * Operations_needed) 來修改它。此步驟透過計算出的減法次數 (Operations_needed * nums ) 減少 array[iterator]，以使其小於或等於 array[ iterator-1 ]。
示例
現在讓我們編寫上述討論的程式碼。上面討論的方法的 C++ 實現如下 -
#include <bits/stdc++.h>
using namespace std;
int min_subtr_opr(int array[], int n, int nums){
int Operations_needed;
int res = 0;
for (int it = 1; it < n; it++) {
Operations_needed = 0;
if (array[it] > array[it - 1]) {
Operations_needed = (array[it] - array[it - 1]) / nums;
if ((array[it] - array[it - 1]) % nums != 0)
Operations_needed++;
array[it] = array[it] - nums * Operations_needed;
}
res = res + Operations_needed;
}
return res;
}
int main() {
int array[] = { 5, 8, 6, 9, 10 };
int n = 5 ;
int nums = 2 ;
cout<< "The minimum number of subtraction operations needed to make the given array:"<< endl;
cout<< "{ ";
for (int it =0; it <n; it ++){
cout<<array[it] << ", ";
}
cout <<"}" << " decreasing is \n" << min_subtr_opr(array, n, nums) << endl;
return 0;
}
輸出
The minimum number of subtraction operations needed to make the given array:
{ 5, 8, 6, 9, 10, } decreasing is
10
時間複雜度 - 我們執行 for 迴圈 n 次，因此程式碼執行所需的時間為 O(N)。
空間複雜度 - 由於我們沒有使用任何額外空間，因此空間複雜度為常數 O(1)。
137 次檢視
