← 返回目录

算法笔试模拟题精解之“破译密码”

第 39 / 74 卷日期：

算法笔试模拟题精解之“破译密码”

贡献者 | 黄信旭

简介：可以使用尺取法来解题；设当前区间为 [L, R]。初始 L = R = 0；使用尺取

法需要判断什么时候调整 L 和 R。

题目描述

题目等级：中等

知识点：尺取法

查看题目：破译密码

给你一个长度为 n 的序列，元素标号 1-n。问能够找到多少对不同的（L,R）（1

<= L <= R），使得在子序列 [L,R] 内存在出现频率不低于 K 的元素？

输入序列大小 n（1 <= n <= 10^4）、出现频率 k（1 <= k <= n）和一个包含 n 个

整数的数组，第 i 个整数表示序列的第 i 个元素为 ai(1 <= ai <= 10^9)。

输出满足条件的子序列个数。

示例 1

输入：

4

2

[1 ,2 ,1 ,2]

输出：

3

注意

三个子序列分别为 [1,3],[1,4],[2,4]

解题思路 : 尺取法

与 57 超级区间那道题是类似的方法。

设当前区间为 [L, R]。初始 L = R = 0；使用尺取法需要判断什么时候调整 L 和 R。

情况 1：假设对于某个区间 [L1, R1] 满足题目要求。则保持 L1 不变，依次增加

R1 直到 n 为止的所有区间都满足题目的要求。

情况 2：假设对于某个区间 [L2，R2] 不满足题目要求。则需要保持 L2 不动，增

加 R2 才可能满足满足题目要求。

情况 3：是情况 2 拓展。如果 [L2，n] 不满足题目要求，则任何 i>L2，区间 [i,

n] 都不满足题目要求。

使用一个 2*n 的数组 numb 来记录当前区间 [L, R] 内每个元素的出现次数。

numbL 和 numbR 表示区间 [L, R] 对应的 numb 数组范围。因为每个数都是按照进

入区间 [L, R] 的顺序离开区间 [L, R] 的，相当于一个队列，所以 numb 数组可以用

numbL 和 numbR 来表示当前区间 [L, R] 内的元素，而不用考虑中间某个数不在区

间 [L, R] 内的情况。

计算过程

  1. 初始 L = R = 0；sum = 0; 用来计算满足条件的区间个数
  2. 判断区间 [L, R] 的情况，满足情况 1，则 sum++; R++。满足情况 2，L++。

满足情况 3，结束计算。

  1. R 每次加 1，都要给 numb 数组中对应的数出现次数 +1。当是一个新数时，

要使 numbR++；

  1. L 每次减 1，都要给 numb 数组中对应的数出现次数 -1。当减为 0 时，要

使 numbL++

对于情况 1，因为 L 不变时，后面的所有 R 都满足条件，所以可以修改为

sum+=n-R+1；L++。

时间复杂度 O(n^2) 修改之前最差为 O(n^2)

空间复杂度 O(2*n) numb 数组的空间

看完之后是不是有了想法了呢，快来练练手吧 >> 查看题目：破译密码

全站分卷索引 · 74 卷
  1. 1一、算法思想
  2. 2算法笔试模拟题精解之“打怪兽”
  3. 31.2 贪心
  4. 4算法笔试模拟题精解之“最强的团队”
  5. 5算法笔试模拟题精解之“Tom 爱吃巧克力”
  6. 6算法笔试模拟题精解之“吃奶酪”
  7. 7算法笔试模拟题精解之“一的个数”
  8. 8算法笔试模拟题精解之“Bob 的花束”
  9. 9算法笔试模拟题精解之“钱庄”
  10. 10算法笔试模拟题精解之“移动射击”
  11. 11算法笔试模拟题精解之“相似数组”
  12. 12算法笔试模拟题精解之“过吊桥”
  13. 13算法笔试模拟题精解之“完美排列”
  14. 14算法笔试模拟题精解之“采摘圣诞果”
  15. 15算法比赛模拟题精解之“Tairitsu and Dynamic Objects”
  16. 16算法笔试模拟题精解之“Codancer 的炸弹引爆”
  17. 17算法笔试模拟题精解之“学习小组”
  18. 18算法笔试模拟题精解之“恢复字符串”
  19. 191.3 DP/ 动态规划
  20. 20算法笔试模拟题精解之“寻找等比数列”
  21. 21算法笔试模拟题精解之“字符配对”
  22. 22算法笔试模拟题精解之“数组染色”
  23. 23算法笔试模拟题精解之“连绵的群山”
  24. 24算法笔试模拟题精解之“难住Tom 的问题”
  25. 25算法笔试模拟题精解之“变化的字符”
  26. 26算法笔试模拟题精解之“跳房子”
  27. 27算法笔试模拟题精解之“寒假活动”
  28. 28算法笔试模拟题精解之“最短路”
  29. 29算法笔试模拟题精解之“codancer 上楼”
  30. 30算法笔试模拟题精解之“木棒拼接”
  31. 31算法笔试模拟题精解之“Codancer 的数组封印”
  32. 32算法笔试模拟题精解之“Jerry 的异或运算”
  33. 33算法笔试模拟题精解之“小明的数学作业”
  34. 34算法笔试模拟题精解之“奇偶数列”
  35. 351.4 剪枝
  36. 361.5 尺取法
  37. 37算法笔试模拟题精解之“调整数组”
  38. 38算法笔试模拟题精解之“最优分组”
  39. 39算法笔试模拟题精解之“破译密码”
  40. 40二、数据结构
  41. 412.2 搜索
  42. 42算法笔试模拟题精解之“能量半径”
  43. 43算法笔试模拟题精解之“苹果收获程序”
  44. 44算法笔试模拟题精解之“恐怖的辐射”
  45. 45算法笔试模拟题精解之“树的拆分”
  46. 46算法笔试模拟题精解之“Password”
  47. 47算法笔试模拟题精解之“神奇数字在哪里”
  48. 48算法笔试模拟题精解之“神奇的棋子”
  49. 492.3 树
  50. 50算法笔试模拟题精解之“Codancer 的旅行”
  51. 51算法笔试模拟题精解之“Codancer 的求和”
  52. 52算法笔试模拟题精解之“找出二叉搜索树的第2 大的数”
  53. 532.4 线型
  54. 54算法笔试模拟题精解之“最活跃的数”
  55. 55算法笔试模拟题精解之“非递减序列”
  56. 56算法笔试模拟题精解之“Tom 跳方格”
  57. 57算法笔试模拟题精解之“复杂的字符串”
  58. 58算法笔试模拟题精解之“神秘消失”
  59. 59三、计算
  60. 60算法笔试模拟题精解之“简单题？
  61. 61算法笔试模拟题精解之“朋友一生一起走”
  62. 62算法笔试模拟题精解之“正三角塔”
  63. 63算法笔试模拟题精解之“组队难题”
  64. 64算法笔试模拟题精解之“2n 合体”
  65. 65算法笔试模拟题精解之“平行线”
  66. 66算法笔试模拟题精解之“叠叠高”
  67. 67算法笔试模拟题精解之“公平”
  68. 68算法笔试模拟题精解之“Tom 的手工课”
  69. 69算法笔试模拟题精解之“填数问题”
  70. 70算法笔试模拟题精解之“Jerry 的考验”
  71. 71算法笔试模拟题精解之“超车”
  72. 72算法笔试模拟题精解之“坏掉的时钟”
  73. 73算法笔试模拟题精解之“期末考试”
  74. 74算法笔试模拟题精解之“滑雪比赛”