Hard

题目描述

给你一个整数数组 nums。nums 的唯一性数组是一个排序后的数组，包含 nums 所有子数组中不同元素的个数。换句话说，这是一个由 distinct(nums[i..j]) 组成的排序数组，其中 0 <= i <= j < nums.length。

这里，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^5
  • 1 <= nums[i] <= 10^5

解题思路

这道题的核心思路是二分答案 + 滑动窗口。

首先分析题目要求：我们需要找到所有子数组的不同元素个数组成的数组的中位数。如果直接枚举所有子数组会超时，因为有 O(n²) 个子数组。

关键洞察：

  1. 二分答案：中位数一定在 [1, n] 范围内（最少1个不同元素，最多n个不同元素）
  2. 单调性：对于某个值 k，如果有足够多的子数组的不同元素个数 ≤ k，那么中位数就 ≤ k
  3. 计数问题：给定 k，如何快速统计不同元素个数 ≤ k 的子数组个数？

对于计数问题，我们使用滑动窗口：

  • 维护一个哈希表记录当前窗口中每个元素的出现次数
  • 对于每个右端点 j，找到最小的左端点 i 使得 distinct(nums[i..j]) ≤ k
  • 此时以 j 为右端点且不同元素个数 ≤ k 的子数组有 (j - i + 1) 个

总的子数组个数为 n*(n+1)/2，中位数位置为 (总数+1)/2。通过二分找到最小的 k，使得不同元素个数 ≤ k 的子数组个数 ≥ 中位数位置。

代码实现

class Solution {
public:
    int medianOfUniquenessArray(vector<int>& nums) {
        int n = nums.size();
        long long total = (long long)n * (n + 1) / 2;
        long long target = (total + 1) / 2;
        
        int left = 1, right = n;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (countSubarrays(nums, mid) >= target) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
    
private:
    long long countSubarrays(vector<int>& nums, int k) {
        int n = nums.size();
        unordered_map<int, int> count;
        long long result = 0;
        int left = 0;
        
        for (int right = 0; right < n; right++) {
            count[nums[right]]++;
            
            while (count.size() > k) {
                count[nums[left]]--;
                if (count[nums[left]] == 0) {
                    count.erase(nums[left]);
                }
                left++;
            }
            
            result += right - left + 1;
        }
        
        return result;
    }
};

class Solution:
    def medianOfUniquenessArray(self, nums: List[int]) -> int:
        n = len(nums)
        total = n * (n + 1) // 2
        target = (total + 1) // 2
        
        def count_subarrays(k):
            count = {}
            result = 0
            left = 0
            
            for right in range(n):
                count[nums[right]] = count.get(nums[right], 0) + 1
                
                while len(count) > k:
                    count[nums[left]] -= 1
                    if count[nums[left]] == 0:
                        del count[nums[left]]
                    left += 1
                
                result += right - left + 1
            
            return result
        
        left, right = 1, n
        while left < right:
            mid = (left + right) // 2
            if count_subarrays(mid) >= target:
                right = mid
            else:
                left = mid + 1
        
        return left

public class Solution {
    public int MedianOfUniquenessArray(int[] nums) {
        int n = nums.Length;
        long total = (long)n * (n + 1) / 2;
        long target = (total + 1) / 2;
        
        int left = 1, right = n;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (CountSubarrays(nums, mid) >= target) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
    
    private long CountSubarrays(int[] nums, int k) {
        int n = nums.Length;
        Dictionary<int, int> count = new Dictionary<int, int>();
        long result = 0;
        int left = 0;
        
        for (int right = 0; right < n; right++) {
            count[nums[right]] = count.GetValueOrDefault(nums[right], 0) + 1;
            
            while (count.Count > k) {
                count[nums[left]]--;
                if (count[nums[left]] == 0) {
                    count.Remove(nums[left]);
                }
                left++;
            }
            
            result += right - left + 1;
        }
        
        return result;
    }
}

var medianOfUniquenessArray = function(nums) {
    const n = nums.length;
    const totalSubarrays = n * (n + 1) / 2;
    const medianPos = Math.ceil(totalSubarrays / 2);
    
    function countSubarraysWithAtMostKDistinct(k) {
        let count = 0;
        let left = 0;
        const freq = new Map();
        
        for (let right = 0; right < n; right++) {
            freq.set(nums[right], (freq.get(nums[right]) || 0) + 1);
            
            while (freq.size > k) {
                freq.set(nums[left], freq.get(nums[left]) - 1);
                if (freq.get(nums[left]) === 0) {
                    freq.delete(nums[left]);
                }
                left++;
            }
            
            count += right - left + 1;
        }
        
        return count;
    }
    
    let left = 1, right = n;
    
    while (left < right) {
        const mid = Math.floor((left + right) / 2);
        const count = countSubarraysWithAtMostKDistinct(mid);
        
        if (count >= medianPos) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    
    return left;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n log n)二分搜索 O(log n)，每次计数需要 O(n)
空间复杂度O(n)哈希表存储不同元素，最多 n 个

相关题目