3371.识别数组中的最大异常值

🎯 问题描述

描述：
给你一个整数数组 nums。
数组中恰好包含一个异常值 $x$ ，其余 $n-1$ 个元素的和可以表示为 $2y$ （即剩余元素的和是偶数，且该和的一半 $y$ 必须存在于剩余元素中）。
数学模型满足方程：

x + 2y = \text{total}

其中：

$x$ 是我们要找的异常值。
$y$ 是剩余元素中的某一个值（基准值）。
total 是数组所有元素之和。

请你返回最大的异常值 $x$ 。

说明：

这是一个哈希表计数结合方程变换的问题。
我们可以通过变换方程 $x + 2y = \text{total}$ ，得到两种不同的解题视角。

💻 解题思路

思路1：枚举异常值 x（正向思维）

核心逻辑

我们尝试假设数组中的每一个数都是异常值 $x$ 。

假设当前数 $x$ 被移除了。
计算剩余元素的和： $S_{rem} = \text{total} - x$ 。
根据方程，剩余元素的和必须等于 $2y$ $2 y$ 。这意味着：
- $S_{rem}$ 必须是偶数。
- 剩余元素中必须包含数值 $y = S_{rem} / 2$ 。

代码实现

class Solution:
    def getLargestOutlier(self, nums: List[int]) -> int:
        ans = -float('inf')
        cnt = Counter(nums)
        total = sum(nums)
        
        # 1. 枚举 x (异常值)
        for x in nums:
            # 临时移除 x
            cnt[x] -= 1
            
            # 2. 计算剩余和
            remaining_sum = total - x
            
            # 3. 验证条件：剩余和必须是偶数，且存在一半的值
            if remaining_sum % 2 == 0:
                target_y = remaining_sum // 2
                if cnt[target_y] > 0:
                    ans = max(ans, x)
            
            # 回溯
            cnt[x] += 1
            
        return ans

优缺点分析

优点：符合直觉，直接寻找目标 $x$ 。
缺点：需要处理奇偶性判断 (% 2 == 0)，逻辑稍微繁琐一点。

思路2：枚举基准值 y（逆向思维/方程变换）

核心逻辑

我们尝试假设数组中的每一个数都是基准值 $y$ 。

利用方程变换： $x = \text{total} - 2y$ 。
假设当前数 $y$ 是基准值，我们直接计算出理论上对应的异常值 $x$ 应该是多少。
检查计算出的 $x$ 是否存在于剩余的数组中。

代码实现

class Solution:
    def getLargestOutlier(self, nums: List[int]) -> int:
        ans = -float('inf')
        cnt = Counter(nums)
        total = sum(nums)
        
        # 1. 枚举 y (基准值)
        for y in nums:
            # 临时移除 y
            cnt[y] -= 1
            
            # 2. 直接计算对应的 x
            potential_x = total - 2 * y
            
            # 3. 验证：计算出的 x 是否存在于剩余数组中？
            # 不需要判断奇偶性，因为 x 可以是任意整数
            if cnt[potential_x] > 0:
                ans = max(ans, potential_x)
            
            # 回溯
            cnt[y] += 1
            
        return ans

优缺点分析

优点：逻辑更简洁。不需要判断奇偶性，直接计算并查找，代码更短，运行通常也稍快（少了一次取模运算）。
缺点：需要转个弯，意识到可以枚举 $y$ 来求 $x$ 。

📊 性能分析

时间复杂度： $O(N)$ $O (N)$
- 两种思路都需要遍历数组一次构建哈希表，再遍历一次进行枚举。
- 哈希表操作均为 $O(1)$ 。
空间复杂度： $O(N)$ $O (N)$
- 都需要 Counter 来存储元素频次。

💡 深度思考

为什么要 cnt[val] -= 1？
- 这是**“借用后归还”**的模式。
- 当我们假设当前的数是 $x$ （或 $y$ ）时，它已经被“使用”了。
- 我们要查找的配对值（ $y$ 或 $x$ ）必须来自剩下的元素。
- 如果不减 1，当 $x == y$ 时（例如数组 [3, 3, 3]，total=9，x=3, y=3），程序可能会错误地认为当前的 $x$ 自己就是那个 $y$ ，导致逻辑错误（除非该数字出现多次）。
为什么思路2更好？
- 思路1 是 $S_{rem} = 2y \Rightarrow y = S_{rem} / 2$ 。这隐含了约束 $S_{rem} \pmod 2 = 0$ 。
- 思路2 是 $x = \text{total} - 2y$ 。这里 $x$ 没有奇偶性约束，任何整数都可以。
- 消除约束通常能让代码更健壮、更简单。
数学之美：
- 同一个方程 $A + B = C$ ，既可以看作“已知 A 求 B”，也可以看作“已知 B 求 A”。在算法题中，灵活变换主元往往是优化的关键。

思路3：排序 + 贪心 + 二分查找

核心逻辑

前两种思路使用了哈希表，时间复杂度为 $O(N)$ ，但需要遍历整个数组。
本思路利用排序和贪心策略：

排序：将数组从小到大排序。
贪心枚举：题目要求最大的异常值。因此，我们从数组末尾向前（从大到小）遍历。
二分查找：对于每一个假设的异常值 $x$ $x$ （代码中的 outlier）：
- 计算剩余和 $S_{rem} = \text{total} - x$ 。
- 若 $S_{rem}$ 为奇数，跳过。
- 若 $S_{rem}$ 为偶数，计算目标基准值 $S = S_{rem} / 2$ 。
- 使用二分查找 (bisect_left) 在数组中查找 $S$ 。
去重验证：
- 如果找到了 $S$ ，需要确保 $S$ 不是我们正在假设的 $x$ 本身（除非数组中有多个 $x$ ）。
- 由于数组已排序，相同的值会相邻。如果找到的 $S$ 的索引与 $x$ 的索引相同，我们需要检查相邻位置是否有相同的值。

代码实现

import bisect

class Solution:
    def getLargestOutlier(self, nums: List[int]) -> int:
        n = len(nums)
        total = sum(nums)
        
        # 1. 排序：为了使用二分查找，也为了支持贪心策略
        nums.sort()
        
        # 2. 从后往前遍历（贪心：优先检查最大的数）
        for i in range(n - 1, -1, -1):
            outlier = nums[i]
            remaining_sum = total - outlier
            
            # 3. 剩余和必须是偶数
            if remaining_sum % 2 != 0:
                continue
                
            S = remaining_sum // 2
            
            # 4. 在数组中二分查找 S
            # bisect_left 返回第一个大于等于 S 的位置
            k = bisect.bisect_left(nums, S)
            
            # 5. 检查是否找到了 S
            if k < n and nums[k] == S:
                # 找到了 S，现在需要确认这个 S 不是我们正在假设的 outlier 本身
                if k != i:
                    # S 和 outlier 是不同的元素（索引不同），直接返回
                    # 因为是从大到小遍历，第一个满足条件的 outlier 就是最大的
                    return outlier
                else:
                    # S 和 outlier 是同一个元素 (nums[i])
                    # 我们需要检查数组中是否还有其他值为 S 的元素
                    # 因为是有序的，只需要检查相邻位置
                    if (k > 0 and nums[k-1] == S) or (k < n - 1 and nums[k+1] == S):
                        return outlier
        
        return -1 # 理论上题目保证有解，这里是为了语法完整

📊 性能分析

时间复杂度： $O(N \log N)$ $O (N lo g N)$
- 排序耗时 $O(N \log N)$ 。
- 遍历数组最坏情况下 $O(N)$ 。
- 每次遍历内部进行二分查找，耗时 $O(\log N)$ 。
- 总时间复杂度为 $O(N \log N)$ 。
- 注：虽然比哈希表的 $O(N)$ 慢，但在实际运行中，如果最大的异常值恰好在数组末尾，这种方法可能更快返回（早停）。
空间复杂度： $O(1)$ $O (1)$ 或 $O(N)$ $O (N)$
- 取决于排序算法的实现（Python 的 sort 是 Timsort，空间复杂度为 $O(N)$ ）。如果不计算排序空间，则为 $O(1)$ 。

💡 思考

贪心策略（早停机制）：
- 题目要求最大的异常值。
- 哈希表方法必须遍历完整个数组才能确定最大值。
- 排序方法可以从大到小遍历，一旦找到合法的异常值，立即返回。在最好的情况下（最大值就是异常值），时间复杂度接近 $O(\log N)$ （排序后直接二分一次）。
二分查找的优势：
- 将查找目标值 $S$ 的时间从哈希表的 $O(1)$ 变成了 $O(\log N)$ ，但换取了空间的节省（不需要哈希表）和逻辑的有序性。
复杂的去重逻辑：
- 这是排序方法的痛点。
- 在哈希表中，我们通过 cnt[val]-- 轻松处理了“借用”问题。
- 在排序数组中，我们需要通过索引来判断。
- 如果 k == i，说明我们想找的基准值 $S$ 恰好就是当前的异常值 $x$ 。
- 此时必须检查 nums[k-1] 或 nums[k+1] 是否也等于 $S$ ，以确认数组中是否有另一个 $S$ 可供使用。
对比三种思路：
- 思路1（枚举 x + 哈希）：逻辑直观，但需处理奇偶性。
- 思路2（枚举 y + 哈希）：逻辑最简，无奇偶判断，推荐。
- 思路3（排序 + 二分）：空间换时间（实际上时间也变慢了），但具备“早停”潜力，适合数据量极大且异常值较大的情况。