具有相同最高数字的最大和对

引言

给定一个非负整数数组，其中每个元素代表一个数字。您的任务是找到数组中的一对数字，使其和最大，并且这两个数字共享相同的最高位数。

编写一个函数 maxSumWithEqualMaxDigits(nums)，该函数接受一个非负整数数组，并返回满足给定条件的一对数字的最大和。如果不存在这样的对，则返回 -1。

方法 1：暴力法

Java 代码

输入

输出

Output: 88

代码解释

1. 代码通过导入 java.util.Scanner 类来读取用户输入。
2. 在 main 方法中，提示用户输入数组的元素数量 (n)。
3. 创建一个大小为 n 的数组 nums 来存储用户提供的元素。
4. 然后提示用户输入数组的每个元素。
5. 调用 maxSum 函数，并将 nums 数组作为参数传递，以计算具有相同最高位数的两个数字的最大和。
6. maxSum 函数使用两个嵌套循环遍历数组中的所有数字对。对于每一对数字，它使用 hasEqualMaxDigits 函数检查它们是否具有相同的最高位数。
7. hasEqualMaxDigits 函数接收两个整数作为输入，并将它们转换为字符串。然后，它比较这两个数字的最高位数。如果最高位数相等，则函数返回 true，表示这两个数字具有相同的最高位数。
8. 最后，显示找到的最大和作为输出。

模拟运行

让我们使用提供的输入 nums = [51, 71, 17, 24, 42] 来模拟代码的运行。

用户输入：n = 5

用户输入数组元素：[51, 71, 17, 24, 42]

现在，让我们逐步执行 maxSum 函数。

遍历所有数字对

• 对 (51, 71)：两个数字的最高位数都是 5。和 = 51 + 71 = 122
• 对 (51, 17)：两个数字的最高位数都是 5。和 = 51 + 17 = 68
• 对 (51, 24)：两个数字的最高位数都是 5。和 = 51 + 24 = 75
• 对 (51, 42)：两个数字的最高位数都是 5。和 = 51 + 42 = 93
• 对 (71, 17)：两个数字的最高位数都是 7。和 = 71 + 17 = 88
• 对 (71, 24)：两个数字的最高位数都是 7。和 = 71 + 24 = 95
• 对 (71, 42)：两个数字的最高位数都是 7。和 = 71 + 42 = 113
• 对 (17, 24)：两个数字的最高位数都是 7。和 = 17 + 24 = 41
• 对 (17, 42)：两个数字的最高位数都是 7。和 = 17 + 42 = 59
• 对 (24, 42)：两个数字的最高位数都是 4。和 = 24 + 42 = 66

具有相同最高位数的两个数字的最大和是 88，对应于对 (71, 17)。

时间复杂度

maxSum 函数使用两个嵌套循环来遍历所有数字对。如果 n 是数组中的元素数量，则最坏情况下的时间复杂度为 O(n^2)。

hasEqualMaxDigits 函数操作字符串，其时间复杂度与字符串长度成线性关系，而字符串长度受输入数字位数的影响。因此，可以认为其时间复杂度为 O(k)，其中 k 是输入数字的最大位数。

空间复杂度

空间复杂度主要取决于输入数组 nums 的存储，需要 O(n) 的空间。

函数中使用的其他变量 (maxSum, hasEqualMaxDigits) 具有恒定的空间复杂度。

方法 2：贪心算法与动态规划的结合

Java 代码

输入

输出

Output: 88

说明

代码解释

1. 代码通过导入 java.util.Scanner 类来读取用户输入。
2. 在 main 方法中，提示用户输入数组的元素数量 (n)。
3. 创建一个大小为 n 的数组 nums 来存储用户提供的元素。
4. 然后提示用户输入数组的每个元素。
5. 调用 maxSum 函数，并将 nums 数组作为参数传递，以计算具有相同最高位数的两个数字的最大和。
6. maxSum 函数使用两个嵌套循环遍历数组中的所有数字对。对于每一对数字，它使用数组 a 和 b 计算它们各自的数字频率。
7. 在计算完正在比较的两个数字的数字频率后，它会检查是否存在一个数字 res (从 9 到 0) 同时存在于这两个数字中。
8. 如果存在这样的数字 res，则表示这两个数字具有相同的最高位数。在这种情况下，如果当前数字对的和大于当前最大和 ans，则更新最大和。
9. 最终返回 ans 作为具有相同最高位数的两个数字的最大和。

模拟运行

让我们使用提供的输入 nums = [51, 71, 17, 24, 42] 来模拟代码的运行。

用户输入：n = 5

用户输入数组元素：[51, 71, 17, 24, 42]

现在，让我们逐步执行 maxSum 函数。

遍历所有数字对

• 对 (51, 71)：最高位数分别是 5 和 7。没有共同的最高位数。继续。
• 对 (51, 17)：最高位数分别是 5 和 7。共同的最高位数：7。更新 ans 为 max(51+17, ans) = max(68, -1) = 68。
• 对 (51, 24)：最高位数分别是 5 和 4。没有共同的最高位数。继续。
• 对 (51, 42)：最高位数分别是 5 和 4。没有共同的最高位数。继续。
• 对 (71, 17)：最高位数分别是 7 和 7。共同的最高位数：7。更新 ans 为 max(71+17, ans) = max(88, 68) = 88。
• 对 (71, 24)：最高位数分别是 7 和 4。没有共同的最高位数。继续。
• 对 (71, 42)：最高位数分别是 7 和 4。没有共同的最高位数。继续。
• 对 (17, 24)：最高位数分别是 7 和 4。没有共同的最高位数。继续。
• 对 (17, 42)：最高位数分别是 7 和 4。没有共同的最高位数。继续。
• 对 (24, 42)：最高位数分别是 4 和 4。共同的最高位数：4。更新 ans 为 max(24+42, ans) = max(66, 88) = 88。

具有相同最高位数的两个数字的最大和是 88，对应于对 (71, 17)。

时间复杂度

maxSum 函数使用两个嵌套循环来遍历所有数字对。如果 n 是数组中的元素数量，则最坏情况下的时间复杂度为 O(n^2)。

嵌套循环涉及使用模运算和除以 10 来处理每个数字的位数。每个数字的位数受输入中最大位数的影响。因此，数字处理具有相对于位数数量的线性时间复杂度。

空间复杂度

空间复杂度主要取决于输入数组 nums 的存储，需要 O(n) 的空间。

函数中使用的其他变量 (a, b, ans, res, first, second, ind) 具有恒定的空间复杂度，因此空间复杂度为 O(1)。