LeetCode 补充题 122. 去重后最大与最小各 N 项之和
题目描述
给你一个 32 位整数数组
nums和一个非负整数N。请先按数值去重，再选出其中最小的N个值和最大的N个值，返回它们的和。两部分不能重叠。如果不同的值不足
2 * N个，返回-1；如果N = 0，返回0。结果使用 64 位整数表示。
示例 1：
输入：
nums = [1,2,2,3,4,5], N = 2
输出：12
解释： 去重后，最小两个值为 1、2，最大两个值为 4、5，和为 12。
示例 2：
输入：
nums = [1,1,2], N = 2
输出：-1
解释： 只有两个不同值，不足以选出互不重叠的两端各两个值。
提示：
- 数组元素为
32位整数。 -
N≥0。 - 按数值去重后两端各选
N个，不允许重叠。 - 不足
2N个不同值返回-1。 -
N=0返回0。
题意分析
选择单位是不同的数值，不是数组位置。因此应先去重，再判断能否选出互不重叠的两组各
N个值。重复次数不会影响某个值是否入选。
解法：去重排序后累加两端不同值
核心思路
[!blue]
将不同值升序排列为
values，长度记为u。最小的N项唯一位于[0,N-1]，最大的N项位于[u-N,u-1]；两段互不重叠当且仅当u >= 2N。数量不足直接返回 -1，否则同步累加左右两端各一项。应在相加之前提升为 64 位，避免两个 32 位整数先溢出；数量比较也用 64 位乘法或
N > u / 2，避免2N溢出。
N = 0时不选任何元素，循环不执行，结果为 0。负数不影响排序选择规则，正常按其数值参与求和。
解题步骤
- 先去重，再对不同值排序。
- 检查不同值数量是否至少为 2N，保证两端选取不重叠。
- 用 64 位累加最前和最后各 N 项；N=0 时结果为 0。
代码实现
class Solution {
public long extremesSum(int[] a, int n) {
int[] values = Arrays.stream(a).distinct().sorted().toArray();
if ((long) values.length < 2L * n) {
return -1;
}
long sum = 0;
for (int i = 0; i < n; i++) {
sum += (long) values[i] + values[values.length - 1 - i];
}
return sum;
}
}
import "sort"
func extremesSum(a []int, n int) int64 {
seen := map[int]bool{}
for _, v := range a {
seen[v] = true
}
values := make([]int, 0, len(seen))
for v := range seen {
values = append(values, v)
}
if n > len(values)/2 {
return -1
}
sort.Ints(values)
sum := int64(0)
for i := 0; i < n; i++ {
sum += int64(values[i]) + int64(values[len(values)-1-i])
}
return sum
}
复杂度分析
- 时间复杂度：期望 $O(L + u \log u)$，
L为输入长度，u为不同值个数；哈希去重后排序。- 空间复杂度：$O(u)$，保存集合及不同值数组。
关键点总结
[!green]
是否足够取数取决于不同值个数，不能用原数组长度判断；求和前提升类型避免单步相加溢出。
易错点总结
[!yellow]
必须先去重再判断数量；不能用原数组长度代替不同值个数。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 414. 第三大的数 | 简单 | 同样按不同值排名，重复元素不能占据多个名次。 |
| 215. 数组中的第K个最大元素 | 中等 | 原题按所有出现次数取第 k 大，本题先去重并同时选择最小与最大两端。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！