[LeetCode] 每日一题 3270. 求出数字答案

题目链接

https://leetcode.cn/problems/find-the-key-of-the-numbers

题目描述

给你三个 正 整数 num1 ，num2 和 num3 。

数字 num1 ，num2 和 num3 的数字答案 key 是一个四位数，定义如下：

• 一开始，如果有数字 少于 四位数，给它补 前导 0 。

• 答案 key 的第 i 个数位（1 <= i <= 4）为 num1 ，num2 和 num3 第 i 个数位中的 最小 值。

请你返回三个数字 没有 前导 0 的数字答案。

示例输入

示例 1

输入：num1 = 1, num2 = 10, num3 = 1000

输出：0

解释：

补前导 0 后，num1 变为 "0001" ，num2 变为 "0010" ，num3 保持不变，为 "1000" 。

数字答案 key 的第 1 个数位为 min(0, 0, 1) 。
数字答案 key 的第 2 个数位为 min(0, 0, 0) 。
数字答案 key 的第 3 个数位为 min(0, 1, 0) 。
数字答案 key 的第 4 个数位为 min(1, 0, 0) 。
所以数字答案为 "0000" ，也就是 0 。

示例 2

输入： num1 = 987, num2 = 879, num3 = 798

输出：777

示例 3

输入：num1 = 1, num2 = 2, num3 = 3

输出：1

提示

• 1 <= num1, num2, num3 <= 9999

题解

解题思路

1. 补齐四位数：为了处理数字可能少于四位的问题，可以在逻辑上将其视为补齐前导 0

2. 逐位处理：从高位到低位逐位比较三个数字当前位的值，取其中的最小值

3. 合成答案：用一个变量 ans 存储结果，按照十进制规则将最小值逐位累加到结果中

4. 更新剩余部分：每次计算完当前位后，使用取余操作更新三个数字，去掉当前最高位

5. 返回结果：最终返回合成的数字

该方法的核心是利用除法和取余操作逐位截取数字，这种方法简洁高效，无需额外空间存储各位数

代码实现

class Solution {
    public int generateKey(int num1, int num2, int num3) {
        // 从最高位开始处理
        int mul = 1000;
        int ans = 0;
        while (mul > 0) {
            // 获取当前位的最小值
            ans += Math.min(num1 / mul, Math.min(num2 / mul, num3 / mul)) * mul;
            // 更新剩余部分
            num1 %= mul;
            num2 %= mul;
            num3 %= mul;
            // 移动到下一位
            mul /= 10;
        }
        return ans;
    }
}

复杂度分析

1. 时间复杂度：

   • 每次循环都处理一位数字，总共有 4 位，因此循环执行 4 次，时间复杂度为 O(1)

   • 每次循环内进行除法、取余和最小值比较，这些操作的时间复杂度均为 O(1)

   • 整体时间复杂度为 O(1)

2. 空间复杂度：

   • 除了 mul 和 ans 两个额外的变量，没有使用其他存储空间，因此空间复杂度为 O(1)

总结

• 该方法通过逐位处理和简单的数学运算实现了问题的高效解决

• 优点是逻辑清晰，代码简洁，且具有常数时间和空间复杂度，非常适合用于处理这种简单的位数比较问题

希望这篇分享能为你带来启发！如果你有任何问题或建议，欢迎在评论区留言，与我共同交流探讨。