What is the median of the uniqueness array?

The median is the middle element in the sorted uniqueness array, or the average of the two middle elements if the array has an even length.

How does binary search help in solving the problem?

Binary search helps narrow down potential median values by focusing on counts of distinct elements within the uniqueness array, improving efficiency.

What pattern does this problem follow?

This problem follows the 'array scanning plus hash lookup' pattern, with an emphasis on efficiently counting distinct elements in subarrays.

Can I use brute force to solve this problem?

Brute force would be too slow for large inputs, so it's recommended to use more efficient methods like hash tables and binary search.

How can I optimize memory usage for this problem?

You can optimize memory usage by using techniques like sliding windows and caching distinct elements, rather than storing all subarrays at once.

#3134

Hard

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

找出唯一性数组的中位数

给你一个整数数组 nums 。数组 nums 的唯一性数组是一个按元素从小到大排序的数组，包含了 nums 的所有非空子数组中不同元素的个数。换句话说，这是由所有 0 的 distinct(nums[i..j]) 组成的递增数组。其中， distinct(nums[i..j]) 表示从下…

数组哈希表二分查找滑动窗口

题目描述

给你一个整数数组 nums 。数组 nums 的 唯一性数组 是一个按元素从小到大排序的数组，包含了 nums 的所有非空子数组中不同元素的个数。

换句话说，这是由所有 0 <= i <= j < nums.length 的 distinct(nums[i..j]) 组成的递增数组。

其中，distinct(nums[i..j]) 表示从下标 i 到下标 j 的子数组中不同元素的数量。

返回 nums 唯一性数组 的 中位数 。

注意，数组的 中位数 定义为有序数组的中间元素。如果有两个中间元素，则取值较小的那个。

示例 1：

输入：nums = [1,2,3]

输出：1

解释：

nums 的唯一性数组为 [distinct(nums[0..0]), distinct(nums[1..1]), distinct(nums[2..2]), distinct(nums[0..1]), distinct(nums[1..2]), distinct(nums[0..2])]，即 [1, 1, 1, 2, 2, 3] 。唯一性数组的中位数为 1 ，因此答案是 1 。

示例 2：

输入：nums = [3,4,3,4,5]

输出：2

解释：

nums 的唯一性数组为 [1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3] 。唯一性数组的中位数为 2 ，因此答案是 2 。

示例 3：

输入：nums = [4,3,5,4]

输出：2

解释：

nums 的唯一性数组为 [1, 1, 1, 1, 2, 2, 2, 3, 3, 3] 。唯一性数组的中位数为 2 ，因此答案是 2 。

提示：

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁵

lightbulb

解题思路

方法一：二分查找 + 双指针

我们记数组 $\textit{nums}$ 的长度为 $n$ ，那么唯一性数组的长度为 $m = \frac{(1 + n) \times n}{2}$ ，而唯一性数组的中位数就是这 $m$ 个数中的第 $\frac{m + 1}{2}$ 小的数字。

考虑唯一性数组中，有多少个数小于等于 $x$ 。随着 $x$ 的增大，只会有越来越多的数小于等于 $x$ 。这存在着单调性，因此，我们可以二分枚举 $x$ ，找到第一个 $x$ ，满足唯一性数组中小于等于 $x$ 的数的个数大于等于 $\frac{m + 1}{2}$ ，这个 $x$ 就是唯一性数组的中位数。

我们定义二分查找的左边界 $l = 0$ ，右边界 $r = n$ ，然后进行二分查找，对于每个 $\textit{mid}$ ，我们检查唯一性数组中小于等于 $\textit{mid}$ 的数的个数是否大于等于 $\frac{m + 1}{2}$ 。我们通过函数 $\text{check}(mx)$ 来实现这一点。

函数 $\text{check}(mx)$ 的实现思路如下：

由于子数组越长，不同元素的个数越多，因此，我们可以利用双指针维护一个滑动窗口，使得窗口中的子数组的不同元素的个数不超过 $mx$ 。具体地，我们维护一个哈希表 $\textit{cnt}$ ， $\textit{cnt}[x]$ 表示窗口中元素 $x$ 的个数。我们使用两个指针 $l$ 和 $r$ ，其中 $l$ 表示窗口的左边界，而 $r$ 表示窗口的右边界。初始时 $l = r = 0$ 。

我们枚举 $r$ ，对于每个 $r$ ，我们将 $\textit{nums}[r]$ 加入窗口中，并更新 $\textit{cnt}[\textit{nums}[r]]$ 。如果窗口中的不同元素的个数超过了 $mx$ ，我们需要将 $l$ 右移，直到窗口中的不同元素的个数不超过 $mx$ 。此时，右端点为 $r$ ，而左端点为 $[l,..r]$ 的子数组都是满足条件的，一共有 $r - l + 1$ 个子数组。我们将这个数量累加到 $k$ 中，如果 $k$ 大于等于 $\frac{m + 1}{2}$ ，那么说明唯一性数组中小于等于 $\textit{mid}$ 的数的个数大于等于 $\frac{m + 1}{2}$ ，我们返回 $\text{true}$ ，否则返回 $\text{false}$ 。

时间复杂度 $O(n \times \log n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为数组 $\textit{nums}$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

class Solution:
    def medianOfUniquenessArray(self, nums: List[int]) -> int:
        def check(mx: int) -> bool:
            cnt = defaultdict(int)
            k = l = 0
            for r, x in enumerate(nums):
                cnt[x] += 1
                while len(cnt) > mx:
                    y = nums[l]
                    cnt[y] -= 1
                    if cnt[y] == 0:
                        cnt.pop(y)
                    l += 1
                k += r - l + 1
                if k >= (m + 1) // 2:
                    return True
            return False

        n = len(nums)
        m = (1 + n) * n // 2
        return bisect_left(range(n), True, key=check)

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
The candidate should demonstrate knowledge of efficient subarray processing, especially using hash tables for distinct element counting.
question_mark
Look for understanding of binary search and its application to this problem for narrowing down the potential median.
question_mark
Candidates should be able to explain memory management strategies for handling large inputs efficiently.

warning

常见陷阱

外企场景

error
Misunderstanding the problem's complexity by using brute-force approaches, leading to time-limit exceeded errors for large inputs.
error
Confusing the median of the uniqueness array with other statistical measures, such as the mean or mode.
error
Not managing memory properly, causing excessive memory usage due to storing all subarrays.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if the input array nums is sorted? Does it change the approach?
arrow_right_alt
How can this problem be adapted to find the mode of the uniqueness array instead of the median?
arrow_right_alt
Can this problem be optimized further with parallel processing or advanced hashing techniques?

help

常见问题

外企场景

继续练习

#2831 找出最长等值子数组 #3143 正方形中的最多点数 #3186 施咒的最大总伤害