题目描述
给你一个整数数组 nums。该数组包含 n 个元素，其中 恰好 有 n - 2 个元素是 特殊数字 。剩下的 两个 元素中，一个是这些 特殊数字 的 和 ，另一个是 异常值 。
异常值 的定义是：既不是原始特殊数字之一，也不是表示这些数字元素和的数字。
注意，特殊数字、和 以及 异常值 的下标必须 不同 ，但可以共享 相同 的值。
返回 nums 中可能的 最大异常值。
示例 1：
输入： nums = [2,3,5,10]
输出： 10
解释：
特殊数字可以是 2 和 3，因此和为 5，异常值为 10。
示例 2：
输入： nums = [-2,-1,-3,-6,4]
输出： 4
解释：
特殊数字可以是 -2、-1 和 -3，因此和为 -6，异常值为 4。
示例 3：
输入： nums = [1,1,1,1,1,5,5]
输出： 5
解释：
特殊数字可以是 1、1、1、1 和 1，因此和为 5，另一个 5 为异常值。
提示：
3 <= nums.length <= 105-1000 <= nums[i] <= 1000- 输入保证
nums 中至少存在 一个 可能的异常值。
解法
方法一：哈希表 + 枚举
我们用一个哈希表 $\textit{cnt}$ 记录数组 $\textit{nums}$ 中每个元素出现的次数。
接下来，我们枚举数组 $\textit{nums}$ 中的每个元素 $x$ 作为可能的异常值，对于每个 $x$，我们计算数组 $\textit{nums}$ 中除了 $x$ 之外的所有元素的和 $t$，如果 $t$ 不是偶数，或者 $t$ 的一半不在 $\textit{cnt}$ 中，那么 $x$ 不满足条件，我们跳过这个 $x$。否则，如果 $x$ 不等于 $t$ 的一半，或者 $x$ 在 $\textit{cnt}$ 中出现的次数大于 $1$，那么 $x$ 是一个可能的异常值，我们更新答案。
枚举结束后，返回答案即可。
时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为数组 $\textit{nums}$ 的长度。
1
2
3
4
5
6
7
8
9
10
11
12 | class Solution:
def getLargestOutlier(self, nums: List[int]) -> int:
s = sum(nums)
cnt = Counter(nums)
ans = -inf
for x, v in cnt.items():
t = s - x
if t % 2 or cnt[t // 2] == 0:
continue
if x != t // 2 or v > 1:
ans = max(ans, x)
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 | class Solution {
public int getLargestOutlier(int[] nums) {
int s = 0;
Map<Integer, Integer> cnt = new HashMap<>();
for (int x : nums) {
s += x;
cnt.merge(x, 1, Integer::sum);
}
int ans = Integer.MIN_VALUE;
for (var e : cnt.entrySet()) {
int x = e.getKey(), v = e.getValue();
int t = s - x;
if (t % 2 != 0 || !cnt.containsKey(t / 2)) {
continue;
}
if (x != t / 2 || v > 1) {
ans = Math.max(ans, x);
}
}
return ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 | class Solution {
public:
int getLargestOutlier(vector<int>& nums) {
int s = 0;
unordered_map<int, int> cnt;
for (int x : nums) {
s += x;
cnt[x]++;
}
int ans = INT_MIN;
for (auto [x, v] : cnt) {
int t = s - x;
if (t % 2 || !cnt.contains(t / 2)) {
continue;
}
if (x != t / 2 || v > 1) {
ans = max(ans, x);
}
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 | func getLargestOutlier(nums []int) int {
s := 0
cnt := map[int]int{}
for _, x := range nums {
s += x
cnt[x]++
}
ans := math.MinInt32
for x, v := range cnt {
t := s - x
if t%2 != 0 || cnt[t/2] == 0 {
continue
}
if x != t/2 || v > 1 {
ans = max(ans, x)
}
}
return ans
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 | function getLargestOutlier(nums: number[]): number {
let s = 0;
const cnt: Record<number, number> = {};
for (const x of nums) {
s += x;
cnt[x] = (cnt[x] || 0) + 1;
}
let ans = -Infinity;
for (const [x, v] of Object.entries(cnt)) {
const t = s - +x;
if (t % 2 || !cnt.hasOwnProperty((t / 2) | 0)) {
continue;
}
if (+x != ((t / 2) | 0) || v > 1) {
ans = Math.max(ans, +x);
}
}
return ans;
}
|