Medium

题目描述

给你一个整数数组 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 <= 10^5
  • -1000 <= nums[i] <= 1000
  • 输入保证至少存在一个潜在的异常值。

提示：

  • 如果我们从数组中移除异常值，数组和的值是多少？
  • 使用哈希表快速查找元素的出现次数。

解题思路

这道题需要理解题意：数组中有 n-2 个特殊数字，1 个和元素，1 个异常值。

核心思路：

  1. 如果我们把某个元素当作异常值移除，剩下的元素中应该有一个是其他所有元素的和
  2. 设总和为 total，异常值为 outlier，和元素为 sum_element
  3. 那么：total - outlier = sum_element + (sum of special numbers)
  4. 而 sum_element = sum of special numbers
  5. 所以：total - outlier = 2 * sum_element
  6. 即：sum_element = (total - outlier) / 2

算法步骤：

  1. 计算数组总和
  2. 使用哈希表记录每个元素的出现次数
  3. 枚举每个可能的异常值，检查对应的和元素是否存在
  4. 注意处理相同值的情况（需要至少2个相同值才能同时作为和元素和异常值）

时间复杂度： O(n) - 遍历数组两次 空间复杂度： O(n) - 哈希表存储

代码实现

class Solution {
public:
    int getLargestOutlier(vector<int>& nums) {
        int total = 0;
        unordered_map<int, int> count;
        
        for (int num : nums) {
            total += num;
            count[num]++;
        }
        
        int maxOutlier = INT_MIN;
        
        for (int outlier : nums) {
            int remaining = total - outlier;
            if (remaining % 2 != 0) continue;
            
            int sumElement = remaining / 2;
            
            // Check if sumElement exists
            if (count.find(sumElement) != count.end()) {
                int needed = (sumElement == outlier) ? 2 : 1;
                if (count[sumElement] >= needed) {
                    maxOutlier = max(maxOutlier, outlier);
                }
            }
        }
        
        return maxOutlier;
    }
};

class Solution:
    def getLargestOutlier(self, nums: List[int]) -> int:
        total = sum(nums)
        count = Counter(nums)
        
        max_outlier = float('-inf')
        
        for outlier in nums:
            remaining = total - outlier
            if remaining % 2 != 0:
                continue
                
            sum_element = remaining // 2
            
            if sum_element in count:
                needed = 2 if sum_element == outlier else 1
                if count[sum_element] >= needed:
                    max_outlier = max(max_outlier, outlier)
        
        return max_outlier

public class Solution {
    public int GetLargestOutlier(int[] nums) {
        int total = nums.Sum();
        var count = new Dictionary<int, int>();
        
        foreach (int num in nums) {
            count[num] = count.GetValueOrDefault(num, 0) + 1;
        }
        
        int maxOutlier = int.MinValue;
        
        foreach (int outlier in nums) {
            int remaining = total - outlier;
            if (remaining % 2 != 0) continue;
            
            int sumElement = remaining / 2;
            
            if (count.ContainsKey(sumElement)) {
                int needed = (sumElement == outlier) ? 2 : 1;
                if (count[sumElement] >= needed) {
                    maxOutlier = Math.Max(maxOutlier, outlier);
                }
            }
        }
        
        return maxOutlier;
    }
}

var getLargestOutlier = function(nums) {
    const total = nums.reduce((sum, num) => sum + num, 0);
    const count = new Map();
    
    for (const num of nums) {
        count.set(num, (count.get(num) || 0) + 1);
    }
    
    let maxOutlier = -Infinity;
    
    for (const outlier of nums) {
        const specialSum = total - outlier;
        
        if (specialSum % 2 !== 0) continue;
        
        const sumElement = specialSum / 2;
        
        let requiredCount = 1;
        if (sumElement === outlier) requiredCount = 2;
        
        if (count.get(sumElement) >= requiredCount) {
            maxOutlier = Math.max(maxOutlier, outlier);
        }
    }
    
    return maxOutlier;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n)需要遍历数组两次，一次计算总和和频次，一次枚举可能的异常值
空间复杂度O(n)哈希表存储每个元素的出现次数，最坏情况下所有元素都不同