周赛20230428

第四题134. 找出唯一性数组的中位数

题目大意：给定一个整数数组nums，唯一性数组是一个按元素从小到大排序的数组，包含了nums的所有非空子数组中不同元素的个数。要求返回nums唯一性数组的中位数，即有序唯一性数组的中间元素。

实现思路：首先，我们需要明确唯一性数组的生成方式，即通过遍历所有非空子数组，计算其中不同元素的个数。然后，我们可以使用二分查找的方法确定唯一性数组的中位数。在二分查找的过程中，我们需要一个辅助函数来判断给定的中位数是否满足条件，即唯一性数组中不同元素的个数大于等于中位数。如果满足条件，我们更新右边界，否则更新左边界，直到左右边界相遇，即找到了唯一性数组的中位数。

class Solution:
    def medianOfUniquenessArray(self, nums: List[int]) -> int:
        n = len(nums)
        k = (n * (n + 1) // 2 + 1) // 2

        def check(mid):
            j, cnt = 0, 0
            fre = Counter()
            for i, num in enumerate(nums):
                fre[num] += 1
                while len(fre) > mid:
                    fre[nums[j]] -= 1
                    if fre[nums[j]] == 0:
                        del fre[nums[j]]
                    j += 1
                cnt += i - j + 1
            return cnt >= k

        l, r = 1, len(set(nums))
        while l < r:
            mid = l + r >> 1
            if check(mid):
                r = mid
            else:
                l = mid + 1
        return l