刷题笔记合集🔗

优雅子数组

问题描述

如果一个数组中出现次数最多的元素出现大于等于 次，被称为 -优雅数组， 也可以被称为优雅阈值。

例如，数组 是一个 -优雅数组，因为元素 出现次数大于等于 次。

而数组 就不是一个 -优雅数组，因为其中出现次数最多的元素是 和 ，只出现了 次。

给定一个数组 和 ，请求出 有多少子数组是 -优雅子数组。

子数组是数组中一个或多个连续元素组成的数组。

例如，数组 包含 个子数组，分别是： , , , , , , , , , 。

输入格式

第一行输入两个整数，以空格隔开，分别表示数组 的长度 和优雅阈值 。

第二行输入数组 的 个元素，以空格隔开。

输出格式

输出一个整数，表示数组 中有多少个子数组是 -优雅子数组。

样例输入

7 3
1 2 3 1 2 3 1

7 2
1 2 3 1 2 3 1

样例输出

1

10

样例	解释说明
样例1	在 时，只有整个数组 是 -优雅子数组，因为只有在这个子数组中元素 出现了 次
样例2	在 时，有 个子数组是 -优雅子数组

数据范围

题解

这道题让我们计算一个有趣的概念："-优雅子数组"的数量。简单地说，就是找到那些包含某个元素出现至少 次的连续子数组。

思路分析

首先，让我们思考一下什么是子数组。子数组是原数组中的一段连续序列。比如数组 [1,2,3]，它的所有子数组是：[1]、[2]、[3]、[1,2]、[2,3]、[1,2,3]。

要解决这个问题，我们可以考虑枚举所有可能的子数组，然后检查每个子数组是否满足"-优雅"的条件。具体做法是：

1. 枚举子数组的左端点 left
2. 从左端点开始，枚举子数组的右端点 right
3. 对于每个 [left, right] 区间，统计区间内各元素出现的次数
4. 如果区间内有元素出现次数≥K，则该子数组是优雅的，结果+1

举个例子，对于数组 [1,2,3,1,2,3,1] 和 K=3：

• 当我们枚举到子数组 [1,2,3,1,2,3,1] 时，发现元素1出现了3次，满足条件
• 而其他所有子数组中，没有任何元素出现次数达到3次

参考代码

• Python

import sys
input = lambda:sys.stdin.readline().strip()

# 读取输入
n, k = map(int, input().split())
arr = list(map(int, input().split()))

def count_elegant_subarrays(nums, k):
    """计算k-优雅子数组的数量"""
    n = len(nums)
    result = 0
    
    # 枚举所有可能的子数组
    for left in range(n):
        # 对于每个左边界，重置计数器
        count = {}  # 用字典统计元素频率
        max_freq = 0  # 跟踪最大频率
        
        # 枚举右边界
        for right in range(left, n):
            # 添加新元素并更新计数
            num = nums[right]
            count[num] = count.get(num, 0) + 1
            max_freq = max(max_freq, count[num])
            
            # 检查是否满足k-优雅条件