Easy
题目描述
给你一个整数数组 nums。你需要找到数组中一对数字的最大和，使得这两个数字的最大数字相等。
例如，2373 由三个不同的数字组成：2、3 和 7，其中 7 是其中最大的。
如果不存在这样的数对，返回 -1，否则返回最大和。
示例 1：
输入：nums = [112,131,411]
输出：-1
解释：每个数字的最大数字按顺序为 [2,3,4]。
示例 2：
输入：nums = [2536,1613,3366,162]
输出：5902
解释：所有数字都有 6 作为它们的最大数字，所以答案是 2536 + 3366 = 5902。
示例 3：
输入：nums = [51,71,17,24,42]
输出：88
解释：每个数字的最大数字按顺序为 [5,7,7,4,4]。
所以我们只有两个可能的数对，71 + 17 = 88 和 24 + 42 = 66。
约束条件：
2 <= nums.length <= 1001 <= nums[i] <= 10^4
提示：
- 找到最大数字等于 x 的最大和第二大元素，其中 1 ≤ x ≤ 9。
解题思路
解题思路
这道题要求找到两个数，使得它们的最大数字相同，并且它们的和最大。
核心思路：
- 对于每个数字，找出其最大数字
- 将具有相同最大数字的数字分组
- 对于每组中的数字，找到最大的两个数字相加
具体步骤：
- 创建一个哈希表，key 为最大数字（0-9），value 为具有该最大数字的所有数字列表
- 遍历数组，对每个数字计算其最大数字，并加入对应的组
- 对每组中的数字进行排序（降序），如果组中至少有两个数字，计算前两个数字的和
- 返回所有可能和中的最大值，如果没有有效的数对则返回 -1
时间复杂度优化： 可以在添加数字到组时就维护每组的最大两个值，避免最后排序的开销。
推荐解法： 使用哈希表分组，然后对每组维护最大的两个值。
代码实现
class Solution {
public:
int maxSum(vector<int>& nums) {
unordered_map<int, vector<int>> groups;
// 分组：按最大数字分组
for (int num : nums) {
int maxDigit = getMaxDigit(num);
groups[maxDigit].push_back(num);
}
int result = -1;
// 对每组找最大的两个数
for (auto& [digit, group] : groups) {
if (group.size() >= 2) {
sort(group.rbegin(), group.rend()); // 降序排序
result = max(result, group[0] + group[1]);
}
}
return result;
}
private:
int getMaxDigit(int num) {
int maxDigit = 0;
while (num > 0) {
maxDigit = max(maxDigit, num % 10);
num /= 10;
}
return maxDigit;
}
};
class Solution:
def maxSum(self, nums: List[int]) -> int:
from collections import defaultdict
def get_max_digit(num):
return max(int(digit) for digit in str(num))
# 按最大数字分组
groups = defaultdict(list)
for num in nums:
max_digit = get_max_digit(num)
groups[max_digit].append(num)
result = -1
# 对每组找最大的两个数
for group in groups.values():
if len(group) >= 2:
group.sort(reverse=True) # 降序排序
result = max(result, group[0] + group[1])
return result
public class Solution {
public int MaxSum(int[] nums) {
Dictionary<int, List<int>> groups = new Dictionary<int, List<int>>();
// 按最大数字分组
foreach (int num in nums) {
int maxDigit = GetMaxDigit(num);
if (!groups.ContainsKey(maxDigit)) {
groups[maxDigit] = new List<int>();
}
groups[maxDigit].Add(num);
}
int result = -1;
// 对每组找最大的两个数
foreach (var group in groups.Values) {
if (group.Count >= 2) {
group.Sort((a, b) => b.CompareTo(a)); // 降序排序
result = Math.Max(result, group[0] + group[1]);
}
}
return result;
}
private int GetMaxDigit(int num) {
int maxDigit = 0;
while (num > 0) {
maxDigit = Math.Max(maxDigit, num % 10);
num /= 10;
}
return maxDigit;
}
}
var maxSum = function(nums) {
function getMaxDigit(num) {
let maxDigit = 0;
while (num > 0) {
maxDigit = Math.max(maxDigit, num % 10);
num = Math.floor(num / 10);
}
return maxDigit;
}
// 按最大数字分组
const groups = new Map();
for (const num of nums) {
const maxDigit = getMaxDigit(num);
if (!groups.has(maxDigit)) {
groups.set(maxDigit, []);
}
groups.get(maxDigit).push(num);
}
let result = -1;
// 对每组找最大的两个数
for (const group of groups.values()) {
if (group.length >= 2) {
group.sort((a, b) => b - a); // 降序排序
result = Math.max(result, group[0] + group[1]);
}
}
return result;
};
复杂度分析
| 复杂度类型 | 分析 |
|---|---|
| 时间复杂度 | O(n log n)，其中 n 是数组长度。主要时间花费在对每组数字的排序上 |
| 空间复杂度 | O(n)，用于存储哈希表中的所有数字 |