建设特效网站,龙岩网站建设全包,北京推广优化经理,网站建设优化公司哪家好来源#xff1a;力扣#xff08;LeetCode#xff09;
描述#xff1a;
给你一个非负整数数组 nums 。在一步操作中#xff0c;你必须#xff1a;
选出一个正整数 x #xff0c;x 需要小于或等于 nums 中 最小 的 非零 元素。nums 中的每个正整数都减去 x。
返回使 n…来源力扣LeetCode
描述
给你一个非负整数数组 nums 。在一步操作中你必须
选出一个正整数 x x 需要小于或等于 nums 中 最小 的 非零 元素。nums 中的每个正整数都减去 x。
返回使 nums 中所有元素都等于 0 需要的 最少 操作数。
示例 1
输入nums [1,5,0,3,5]
输出3
解释
第一步操作选出 x 1 之后 nums [0,4,0,2,4] 。
第二步操作选出 x 2 之后 nums [0,2,0,0,2] 。
第三步操作选出 x 2 之后 nums [0,0,0,0,0] 。示例 2
输入nums [0]
输出0
解释nums 中的每个元素都已经是 0 所以不需要执行任何操作。提示
1 nums.length 1000 nums[i] 100
方法一排序 模拟
这道题要求计算将非负整数数组 nums 中的所有元素减少到 0 的最少操作数。用 m 表示数组 nums 中的最小非零元素则可以选择不超过 m 的正整数 x将数组中的每个非零元素减 x。为了使操作数最少应选择 x m理由如下。
当选择 x m 时经过一次操作之后数组中的所有元素 m 都变成 0且其余的所有非零元素都减少 m。当选择 x m 时经过一次操作之后数组中的所有元素 m 在减少 x 之后仍大于 0为了使数组中的最小非零元素变成 0至少还需要一次操作因此至少需要两次操作使数组中的所有元素 m 都变成 0且其余的所有非零元素都减少 m。
由于当 x m 时使元素 m 变成 0 的操作数大于当 x m 时使元素 m 变成 0 的操作数且两种方案中使元素 m 变成 0 之后剩余的最小非零元素相同所有非零元素都减少 m因此只有当 x m 时才能使操作数最少。
根据上述分析应使用贪心策略使操作数最少贪心策略为每次选择数组中的最小非零元素作为 x将数组中的每个非零元素减 x。
可以根据贪心策略模拟操作过程计算最少操作数。
首先将数组 nums 按升序排序然后从左到右遍历排序后的数组 nums。对于每个遍历到的非零元素该元素是数组中的最小非零元素将该元素记为 x将数组中的每个非零元素都减 x将操作数加 1。遍历结束之后即可得到最少操作数。
代码
class Solution {
public:void subtract(vectorint nums, int x, int startIndex) {int length nums.size();for (int i startIndex; i length; i) {nums[i] - x;}}int minimumOperations(vectorint nums) {int ans 0;sort(nums.begin(), nums.end());int length nums.size();for (int i 0; i length; i) {if (nums[i] 0) {subtract(nums, nums[i], i);ans;}}return ans;}
};执行用时0 ms, 在所有 C 提交中击败了100.00%的用户 内存消耗7.9 MB, 在所有 C 提交中击败了100.00%的用户 复杂度分析 时间复杂度O(n2)其中 n 是数组 nums 的长度。排序需要 O(nlogn) 的时间排序之后需要遍历数组一次对于每个非零元素将数组中的所有非零元素减去最小非零元素需要 O(n) 的时间因此时间复杂度是 O(n2)。 空间复杂度O(logn)其中 n 是数组 nums 的长度。排序需要 O(logn) 的递归调用栈空间。 方法二哈希集合
由于每次操作都将数组中的所有非零元素减少一个相同的值因此数组中的相等元素减少到 0 的操作数相等数组中的不相等元素减少到 0 的操作数不相等。
又由于使用贪心策略操作时每次操作都会将数组中的最小非零元素减少到 0因此最少操作数等于数组中的不同非零元素的个数。
使用哈希集合存储数组中的所有非零元素则哈希集合的大小等于数组中的不同非零元素的个数即为最少操作数。
需要注意的是由于目标是将数组中的所有元素减少 0如果数组中的一个元素已经是 0 则不需要对该元素执行操作因此只需要考虑数组中的不同非零元素的个数。
代码
class Solution {
public:int minimumOperations(vectorint nums) {unordered_setint hashSet;for (int num : nums) {if (num 0) {hashSet.emplace(num);}}return hashSet.size();}
};执行用时0 ms, 在所有 C 提交中击败了100.00%的用户 内存消耗8.2 MB, 在所有 C 提交中击败了28.86%的用户 复杂度分析 时间复杂度O(n)其中 n 是数组 nums 的长度。需要遍历数组一次每个非零元素加入哈希集合的时间是 O(1)。 空间复杂度O(n)其中 n 是数组 nums 的长度。哈希集合需要 O(n) 的空间。 authorLeetCode-Solution
