• Home
  • Features
  • Pricing
  • Docs
  • Announcements
  • Sign In

yi-ge / cpp-practice / 7318424122

25 Dec 2023 02:22AM UTC coverage: 81.934% (-0.01%) from 81.945%
7318424122

push

github

yi-ge
add: 不浪费原料的汉堡制作方案

2948 of 4443 branches covered (0.0%)

Branch coverage included in aggregate %.

12 of 12 new or added lines in 1 file covered. (100.0%)

1 existing line in 1 file now uncovered.

6594 of 7203 relevant lines covered (91.55%)

32951.5 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

76.92
/src/array/online_majority_element_in_subarray.cpp
1
// 子数组中占绝大多数的元素
2
// https://leetcode.cn/problems/online-majority-element-in-subarray
3
// INLINE  ../../images/array/online_majority_element_in_subarray.jpeg
4
// 官方题解
5

6
#include <headers.hpp>
7
#include <random>
8

9
class MajorityChecker {
10
public:
11
  // 构造函数,将数组中每个元素的位置存储到哈希表中
12
  MajorityChecker(vector<int> &arr) : arr(arr) {
2✔
13
    for (int i = 0; i < arr.size(); ++i) {
14✔
14
      loc[arr[i]].push_back(i);
12!
15
    }
12✔
16
  }
2✔
17

18
  // 查询函数,随机从[left, right]范围内选择k个数,统计每个数在子数组中出现的次数,如果有数出现次数超过threshold,则返回该数,否则返回-1
19
  int query(int left, int right, int threshold) {
6✔
20
    int length = right - left + 1;
6✔
21
    uniform_int_distribution<int> dis(left, right);
6✔
22

23
    for (int i = 0; i < k; ++i) {
6!
24
      int x = arr[dis(gen)]; // 随机选择一个数
6✔
25
      vector<int> &pos = loc[x]; // 获取该数在数组中出现的位置
6✔
26
      int occ = upper_bound(pos.begin(), pos.end(), right) - // 统计该数在子数组中出现的次数
12✔
27
                lower_bound(pos.begin(), pos.end(), left);
6✔
28
      if (occ >= threshold) { // 如果该数在子数组中出现的次数超过threshold,则返回该数
6✔
29
        return x;
4✔
30
      } else if (occ * 2 >= length) { // 如果该数在子数组中出现的次数小于threshold,但是在子数组中占比超过1/2,则返回-1
2!
31
        return -1;
2✔
32
      } // LCOV_EXCL_LINE
UNCOV
33
    }   // LCOV_EXCL_LINE
×
34

35
    return -1; // LCOV_EXCL_LINE
×
36
  }
6✔
37

38
private:
39
  static constexpr int k = 20; // 随机选择数的个数
40

41
  const vector<int> &arr; // 存储原始数组
42
  unordered_map<int, vector<int>> loc; // 哈希表,存储每个数在数组中出现的位置
43
  mt19937 gen{random_device{}()}; // 随机数生成器
2!
44
};
45

46
/**
47
 * Your MajorityChecker object will be instantiated and called as such:
48
 * MajorityChecker* obj = new MajorityChecker(arr);
49
 * int param_1 = obj->query(left,right,threshold);
50
 */
STATUS · Troubleshooting · Open an Issue · Sales · Support · CAREERS · ENTERPRISE · START FREE · SCHEDULE DEMO
ANNOUNCEMENTS · TWITTER · TOS & SLA · Supported CI Services · What's a CI service? · Automated Testing

© 2026 Coveralls, Inc