跳转至

3353. Minimum Total Operations 🔒

题目描述

Given an array of integers nums, you can perform any number of operations on this array.

In each operation, you can:

  • Choose a prefix of the array.
  • Choose an integer k (which can be negative) and add k to each element in the chosen prefix.

A prefix of an array is a subarray that starts from the beginning of the array and extends to any point within it.

Return the minimum number of operations required to make all elements in arr equal.

 

Example 1:

Input: nums = [1,4,2]

Output: 2

Explanation:

  • Operation 1: Choose the prefix [1, 4] of length 2 and add -2 to each element of the prefix. The array becomes [-1, 2, 2].
  • Operation 2: Choose the prefix [-1] of length 1 and add 3 to it. The array becomes [2, 2, 2].
  • Thus, the minimum number of required operations is 2.

Example 2:

Input: nums = [10,10,10]

Output: 0

Explanation:

  • All elements are already equal, so no operations are needed.

 

Constraints:

  • 1 <= nums.length <= 105
  • -109 <= nums[i] <= 109

解法

方法一：一次遍历

我们可以遍历数组，对于每个元素，如果它与前一个元素不相等，那么就需要进行一次操作，最后返回操作的次数即可。

时间复杂度 $O(n)$，其中 $n$ 为数组的长度。空间复杂度 $O(1)$。

1
2
3
class Solution:
    def minOperations(self, nums: List[int]) -> int:
        return sum(x != y for x, y in pairwise(nums))

1
2
3
4
5
6
7
8
9
class Solution {
    public int minOperations(int[] nums) {
        int ans = 0;
        for (int i = 1; i < nums.length; ++i) {
            ans += nums[i] != nums[i - 1] ? 1 : 0;
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution {
public:
    int minOperations(vector<int>& nums) {
        int ans = 0;
        for (int i = 1; i < nums.size(); ++i) {
            ans += nums[i] != nums[i - 1];
        }
        return ans;
    }
};

1
2
3
4
5
6
7
8
func minOperations(nums []int) (ans int) {
    for i, x := range nums[1:] {
        if x != nums[i] {
            ans++
        }
    }
    return
}

1
2
3
4
5
6
7
function minOperations(nums: number[]): number {
    let ans = 0;
    for (let i = 1; i < nums.length; ++i) {
        ans += nums[i] !== nums[i - 1] ? 1 : 0;
    }
    return ans;
}

评论