公司网站更新,有没有做网页的兼职网站,快速做网站软件,做投资网站目录 一、问题描述二、示例及约束三、代码方法一#xff1a;排序方法二#xff1a;取最小值 四、总结 一、问题描述 给你一个长度为 n 的整数数组#xff0c;每次操作将会使 n - 1 个元素增加 1 。返回让数组所有元素相等的最小操作次数。
二、示例及约束
示例 1#xff… 目录 一、问题描述二、示例及约束三、代码方法一排序方法二取最小值 四、总结 一、问题描述 给你一个长度为 n 的整数数组每次操作将会使 n - 1 个元素增加 1 。返回让数组所有元素相等的最小操作次数。
二、示例及约束
示例 1 输入 nums [1,2,3] 输出 3 解释 只需要3次操作注意每次操作会增加两个元素的值 [1,2,3] [2,3,3] [3,4,3] [4,4,4]
示例 2 输入 nums [1,1,1] 输出 0
提示 ● n nums.length ● 1 n 1 0 5 10^5 105 ● − 1 0 9 -10^9 −109 nums[i] 1 0 9 10^9 109 ● 答案保证符合 32-bit 整数
三、代码
方法一排序
//n - 1个元素增加1本质上等效于让最大元素减少1那么次数也就相当于所有数与最小数做差之后求和
class Solution {
public:int minMoves(vectorint nums) {int count 0, n nums.size();sort(nums.begin(), nums.end());for (int i 1; i n; i) {//排序之后第一个数最小因此从第二个数开始if (nums[i] nums[0]) {count nums[i] - nums[0];//做差并求和//nums[i] nums[0];等同于增加1的反向操作}}return count;}
};方法二取最小值
//排序本质上其实是为了找最小值那么其实可以不用排序来省掉这部分排序时间
class Solution {
public:int minMoves(vectorint nums) {/*min_element是C标准模板库STL中的一个算法它用于在容器如数组、向量等中查找并返回指向最小元素的迭代器。以min_element (ForwardIterator first, ForwardIterator last)为例first和last是指向容器中范围的迭代器位置表示要查找最小值的元素的范围。函数返回一个指向该范围内最小元素的迭代器。如果找到多个最小元素函数将返回最先找到的那个。min_element返回指向最小元素的迭代器而*操作符用于解引用这个迭代器从而获取它所指向的元素的值。*/int minNum *min_element(nums.begin(),nums.end());int res 0;for (int num : nums) {res num - minNum;}return res;}
};四、总结
时间复杂度 方法一O(nlogn)sort排序开销。 方法二O(n)其中 n 是数组 nums 的长度。 空间复杂度 方法一O(1)。 方法二O(1)。
方法时间复杂度空间复杂度方法一O( n l o g n nlogn nlogn)O(1)方法二O( n n n)O(1)
