【Leetcode Daily】3371识别数组中的最大异常值

题目浅析

• 想查看原题可以点击题目链接。

• 简单地说，就是给一个整型数组，数组中分三种值，特殊数字，特殊数字的和，异常值，要求找到数组中可能要在的异常值的最大的值，并且异常值和特殊数字的和必须不同，但可以共享相同的值。

思路分享

• 面对这种有几个类型的值的情况，可以用未知数列出关系，从而窥见规律得以解题。

  https://leetcode.cn/problems/identify-the-largest-outlier-in-an-array/solutions/3006328/mei-ju-yi-chang-zhi-pythonjavacgo-by-end-wb3g/

• 首先设我们要求的异常值为 x，剩下的特殊值之和为 y，那么整个数组的和 total=x+2*y（剩下的特殊值的数值和也是 y 嘛）。那么现在我们就可以发现，这就是 【Leetcode Daily】1两数之和。

• O(n)枚举的基本思路，可以看 【Leetcode Daily】1两数之和。

• 有两种枚举方式

  • 一种是枚举异常值 x，那么就得要先计算 total - x求 y*2，进一步求 y。然后要确保 y 在数组中存在，以及 y 和 x 不是一个值的情况下，记录异常值的最大值；
  • 另一种枚举特殊值 y，那么先计算 x=total-2*y，然后检查 x 在数组中，且 x 可以不与 y 重合的情况下，就记录异常值的最大值。

代码解答（强烈建议自行解答后再看）

• 参考题解

class Solution:
    def getLargestOutlier(self, nums: List[int]) -> int:
        # x + 2*y = total x是异常值，y是特殊数字和
        # 如果尝试枚举 y，就得下面这样子
        # rec = Counter(nums)
        # total = sum(nums)
        # max_num = -inf
        # for num in nums:
        #     x = total-2*num
        #     if rec[x] and (x!=num or rec[x]>1):
        #         max_num = max(max_num, x)
        # return max_num
        # 如果想枚举 x
        rec = Counter(nums)
        total = sum(nums)
        max_num = -inf
        for x in nums:
            num, left = divmod(total-x, 2)
            if left == 0 and rec[num] and (x!=num or rec[num]>1):
                max_num  = max(max_num, x)
        return max_num