Easy

题目描述

给你一个整数数组 nums。

你需要将 nums 中的每个元素替换为其各位数字之和。

返回所有替换操作完成后 nums 中的最小元素。

示例 1：

输入：nums = [10,12,13,14]
输出：1
解释：
所有替换操作完成后，nums 变为 [1, 3, 4, 5]，最小元素为 1。

示例 2：

输入：nums = [1,2,3,4]
输出：1
解释：
所有替换操作完成后，nums 变为 [1, 2, 3, 4]，最小元素为 1。

示例 3：

输入：nums = [999,19,199]
输出：10
解释：
所有替换操作完成后，nums 变为 [27, 10, 19]，最小元素为 10。

约束条件：

  • 1 <= nums.length <= 100
  • 1 <= nums[i] <= 10^4

提示：

  • 将数字转换为字符串并计算每个元素的各位数字之和。

解题思路

解题思路

这道题的核心是计算每个数字的各位数字之和，然后找出最小值。

主要步骤：

  1. 计算各位数字之和：对于每个数字，我们需要提取其每一位数字并求和

    • 方法1：转换为字符串，遍历每个字符
    • 方法2：使用数学运算，不断取模和整除

  2. 找最小值：在所有转换后的数字中找到最小值

算法实现：

对于计算各位数字之和，推荐使用数学方法：

  • 使用 num % 10 获取最后一位数字
  • 使用 num /= 10 去掉最后一位
  • 重复直到数字为0

时间复杂度分析：

  • 对于每个数字，计算各位数字之和的时间复杂度为 O(log num)
  • 总时间复杂度为 O(n × log max(nums))

这种方法简洁高效，避免了字符串转换的开销。

代码实现

class Solution {
public:
    int minElement(vector<int>& nums) {
        int minVal = INT_MAX;
        
        for (int num : nums) {
            int digitSum = 0;
            while (num > 0) {
                digitSum += num % 10;
                num /= 10;
            }
            minVal = min(minVal, digitSum);
        }
        
        return minVal;
    }
};

class Solution:
    def minElement(self, nums: List[int]) -> int:
        def digit_sum(num):
            total = 0
            while num > 0:
                total += num % 10
                num //= 10
            return total
        
        return min(digit_sum(num) for num in nums)

public class Solution {
    public int MinElement(int[] nums) {
        int minVal = int.MaxValue;
        
        foreach (int num in nums) {
            int digitSum = 0;
            int temp = num;
            while (temp > 0) {
                digitSum += temp % 10;
                temp /= 10;
            }
            minVal = Math.Min(minVal, digitSum);
        }
        
        return minVal;
    }
}

var minElement = function(nums) {
    function digitSum(num) {
        let sum = 0;
        while (num > 0) {
            sum += num % 10;
            num = Math.floor(num / 10);
        }
        return sum;
    }
    
    return Math.min(...nums.map(digitSum));
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度
时间复杂度O(n × log(max(nums)))
空间复杂度O(1)

其中 n 是数组长度，log(max(nums)) 是最大数字的位数。

相关题目