Easy

题目描述

给你一个整数数组 nums。在一次操作中，你可以对 nums 的任意元素加 1 或减 1。

返回使 nums 中所有元素都能被 3 整除所需的最少操作次数。

示例 1：

输入：nums = [1,2,3,4]
输出：3
解释：
可以用 3 次操作使所有数组元素都能被 3 整除：
- 将 1 减 1。
- 将 2 加 1。
- 将 4 减 1。

示例 2：

输入：nums = [3,6,9]
输出：0

提示：

  • 1 <= nums.length <= 50
  • 1 <= nums[i] <= 50

解题思路

解题思路

这道题的关键在于理解如何让一个数变成能被3整除的数。对于任意整数 x，我们需要分析 x % 3 的余数情况：

  1. 余数为0：已经能被3整除，不需要操作
  2. 余数为1：可以减1变成能被3整除，需要1次操作
  3. 余数为2：可以加1变成能被3整除，需要1次操作

更一般地，对于余数为 r 的数，我们有两种选择：

  • 减去 r，使其变成最近的较小的3的倍数
  • 加上 (3-r)，使其变成最近的较大的3的倍数

因此，最少操作次数为 min(r, 3-r)。

算法步骤：

  1. 遍历数组中的每个元素
  2. 计算每个元素对3的余数
  3. 对于每个余数，计算最少需要的操作次数
  4. 累加所有操作次数

这是一个贪心算法，因为对于每个元素，我们都选择使其变成3的倍数的最优操作方案。

代码实现

class Solution {
public:
    int minimumOperations(vector<int>& nums) {
        int operations = 0;
        for (int num : nums) {
            int remainder = num % 3;
            if (remainder != 0) {
                operations += min(remainder, 3 - remainder);
            }
        }
        return operations;
    }
};

class Solution:
    def minimumOperations(self, nums: List[int]) -> int:
        operations = 0
        for num in nums:
            remainder = num % 3
            if remainder != 0:
                operations += min(remainder, 3 - remainder)
        return operations

public class Solution {
    public int MinimumOperations(int[] nums) {
        int operations = 0;
        foreach (int num in nums) {
            int remainder = num % 3;
            if (remainder != 0) {
                operations += Math.Min(remainder, 3 - remainder);
            }
        }
        return operations;
    }
}

var minimumOperations = function(nums) {
    let operations = 0;
    for (let num of nums) {
        let remainder = num % 3;
        if (remainder !== 0) {
            operations += Math.min(remainder, 3 - remainder);
        }
    }
    return operations;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历数组一次，其中 n 是数组长度
空间复杂度O(1)只使用常数级别的额外空间

相关题目