数组中的最大数对和
难度:
标签:
题目描述
You are given a 0-indexed integer array nums. You have to find the maximum sum of a pair of numbers from nums such that the maximum digit in both numbers are equal.
Return the maximum sum or -1 if no such pair exists.
Example 1:
Input: nums = [51,71,17,24,42] Output: 88 Explanation: For i = 1 and j = 2, nums[i] and nums[j] have equal maximum digits with a pair sum of 71 + 17 = 88. For i = 3 and j = 4, nums[i] and nums[j] have equal maximum digits with a pair sum of 24 + 42 = 66. It can be shown that there are no other pairs with equal maximum digits, so the answer is 88.
Example 2:
Input: nums = [1,2,3,4] Output: -1 Explanation: No pair exists in nums with equal maximum digits.
Constraints:
2 <= nums.length <= 1001 <= nums[i] <= 104
代码结果
运行时间: 58 ms, 内存: 16.0 MB
/*
* 思路：
* 1. 使用Java Streams来遍历和处理数组。
* 2. 使用Collectors.groupingBy将具有相同最大数字的数分组。
* 3. 对每个分组的元素排序并取出前两个进行和的计算。
* 4. 返回找到的最大和，如果没有找到满足条件的数对，返回-1。
*/
import java.util.*;
import java.util.stream.*;
public class MaxPairSumStream {
public int maxSum(int[] nums) {
return Arrays.stream(nums)
.boxed()
.collect(Collectors.groupingBy(this::getMaxDigit))
.values()
.stream()
.mapToInt(group -> group.stream()
.sorted(Collections.reverseOrder())
.limit(2)
.reduce(Integer::sum)
.orElse(-1))
.max()
.orElse(-1);
}
private int getMaxDigit(int num) {
return String.valueOf(num).chars()
.map(Character::getNumericValue)
.max()
.orElse(0);
}
}
解释
方法:
该题解采用哈希表的方法。首先，遍历数组nums，对于每个元素x，将其转换为字符串，然后找出其数位上的最大数字，将x添加到以该最大数字为键的哈希表d的对应列表中。这样，哈希表d的每个键对应的列表中都是数位上最大数字相同的元素。接着，遍历哈希表d的每个值（即列表），如果列表长度大于等于2，说明存在至少两个数位上最大数字相同的元素，计算这两个元素的和（取列表中最大的两个元素求和），并更新最大和。最后，返回最大和，如果不存在满足条件的数对，则返回-1。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
如何有效地从整数中找到其数位上的最大数字，并确定这种方法是否最优？
▷🦆
在哈希表的每个列表中，为什么选择只取最大的两个元素进行求和而不是考虑其他组合？
▷🦆
如果数组中的数字有多个且相同，这种情况下的处理是否会影响最终求和的结果？
▷🦆
在实际情况下，哈希表的键的数量m通常小于数组长度n的说法是否总是成立？能否给出实际的例子说明？
▷