数据结构
网络
关系型数据库管理系统
操作系统
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 次查看
