3300. 替换为数位和以后的最小元素

English Version

题目描述

给你一个整数数组 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] <= 104

解法

方法一：模拟

我们可以遍历数组 $\textit{nums}$，对于每个数 $x$，我们计算其各个数位之和 $y$，取所有 $y$ 中的最小值即为答案。

时间复杂度 $O(n \times \log M)$，其中 $n$ 和 $M$ 分别是数组 $\textit{nums}$ 的长度和数组中的最大值。空间复杂度 $O(1)$。

Python3

class Solution:
    def minElement(self, nums: List[int]) -> int:
        return min(sum(int(b) for b in str(x)) for x in nums)

Java

class Solution {
    public int minElement(int[] nums) {
        int ans = 100;
        for (int x : nums) {
            int y = 0;
            for (; x > 0; x /= 10) {
                y += x % 10;
            }
            ans = Math.min(ans, y);
        }
        return ans;
    }
}

C++

class Solution {
public:
    int minElement(vector<int>& nums) {
        int ans = 100;
        for (int x : nums) {
            int y = 0;
            for (; x > 0; x /= 10) {
                y += x % 10;
            }
            ans = min(ans, y);
        }
        return ans;
    }
};

Go

func minElement(nums []int) int {
	ans := 100
	for _, x := range nums {
		y := 0
		for ; x > 0; x /= 10 {
			y += x % 10
		}
		ans = min(ans, y)
	}
	return ans
}

TypeScript

function minElement(nums: number[]): number {
    let ans: number = 100;
    for (let x of nums) {
        let y = 0;
        for (; x; x = Math.floor(x / 10)) {
            y += x % 10;
        }
        ans = Math.min(ans, y);
    }
    return ans;
}