众数 I - 解题思路与代码实现

解题思路\n\n首先，我们需要明确题目所给的操作是将序列中的某个元素修改为任意整数，也就是说可以将一个元素修改为另一个元素。因此，我们可以通过修改序列中的某些元素，使得它们的出现次数最多的数的出现次数达到最大。\n\n接下来，我们需要考虑每个元素在序列中出现的位置。由于我们可以修改序列中的元素，因此对于一个数来说，它在序列中的任意一个位置都可以成为众数。我们可以将每个元素出现的位置看作一个区间，然后我们需要判断这些区间是否重叠。\n\n假设 $a_i$ 在序列中的位置是 $l_i$ 到 $r_i$，如果存在两个数 $a_i$ 和 $a_j$ 使得 $r_i < l_j$ 或者 $r_j < l_i$，那么它们的区间是不重叠的。反之，如果对于任意的两个数 $a_i$ 和 $a_j$，都有 $r_i \geq l_j$ 和 $r_j \geq l_i$，那么它们的区间是重叠的。\n\n如果存在两个区间是重叠的，那么我们可以通过修改序列中的元素，使得它们的出现次数最多的数的出现次数达到最大，因此答案为正无穷。否则，我们需要找到所有区间的并集，并统计并集中的元素个数。\n\n算法步骤\n\n1. 统计每个元素在序列中出现的位置，得到每个元素的区间。\n2. 判断每两个区间是否重叠，如果存在两个区间重叠则输出 "pigstd"。\n3. 否则，找到所有区间的并集，并统计并集中的元素个数。\n\n复杂度分析\n\n统计每个元素在序列中出现的位置需要遍历一次序列，时间复杂度为 $O(n)$。\n\n判断每两个区间是否重叠需要遍历一次区间，时间复杂度为 $O(n)$。\n\n统计并集中的元素个数需要遍历一次区间并使用哈希表记录每个元素的出现次数，时间复杂度为 $O(n)$。\n\n综上所述，总的时间复杂度为 $O(n)$。\n\n代码实现\n\npython\ndef findMajority(n, k, a):\n # 统计每个元素在序列中出现的位置\n positions = {}\n for i in range(n):\n if a[i] not in positions:\n positions[a[i]] = [i, i]\n else:\n positions[a[i]][1] = i\n \n # 判断每两个区间是否重叠\n for i in range(1, n):\n if positions[a[i]][1] < positions[a[i-1]][0] or positions[a[i-1]][1] < positions[a[i]][0]:\n return "pigstd"\n \n # 统计并集中的元素个数\n count = set()\n for pos in positions.values():\n for i in range(pos[0], pos[1] + 1):\n count.add(a[i])\n \n return len(count)\n\n# 读取输入\n n, k = map(int, input().split())\n a = list(map(int, input().split()))\n\n# 调用函数并输出结果\n print(findMajority(n, k, a))\n\n\n总结\n\n本题考察了对序列和区间的处理。通过统计每个元素在序列中出现的位置，判断每两个区间是否重叠，然后找到所有区间的并集。