ᕕ( ᐛ )ᕗ Jimyag's Blog

LeetCode-911-在线选举

题目

给你两个整数数组 persons 和 times。在选举中，第 i 张票是在时刻为 times[i] 时投给候选人 persons[i] 的。

对于发生在时刻 t 的每个查询，需要找出在 t 时刻在选举中领先的候选人的编号。

在 t 时刻投出的选票也将被计入我们的查询之中。在平局的情况下，最近获得投票的候选人将会获胜。

实现 TopVotedCandidate 类：

TopVotedCandidate(int[] persons, int[] times) 使用 persons 和 times 数组初始化对象。 int q(int t) 根据前面描述的规则，返回在时刻 t 在选举中领先的候选人的编号。

示例

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

输入：
["TopVotedCandidate", "q", "q", "q", "q", "q", "q"]
[[[0, 1, 1, 0, 0, 1, 0], [0, 5, 10, 15, 20, 25, 30]], [3], [12], [25], [15], [24], [8]]
输出：
[null, 0, 1, 1, 0, 0, 1]

解释：
TopVotedCandidate topVotedCandidate = new TopVotedCandidate([0, 1, 1, 0, 0, 1, 0], [0, 5, 10, 15, 20, 25, 30]);
topVotedCandidate.q(3); // 返回 0，在时刻 3，票数分布为 [0] ，编号为 0 的候选人领先。
topVotedCandidate.q(12); // 返回 1，在时刻 12，票数分布为 [0,1,1] ，编号为 1 的候选人领先。
topVotedCandidate.q(25); // 返回 1，在时刻 25，票数分布为 [0,1,1,0,0,1] ，编号为 1 的候选人领先。（在平局的情况下，1 是最近获得投票的候选人）。
topVotedCandidate.q(15); // 返回 0
topVotedCandidate.q(24); // 返回 0
topVotedCandidate.q(8); // 返回 1

解释

对于给的示例进行解释，

首先初始化投票信息。

投给的候选人 时间 当前0候选人票数 当前1候选人票数 当前时间段领先的候选人
0 号 0 1 票 0 票 0 号
1 号 5 1 票 1 票（最近被投的） 1 号（最近被投的领先）
1 号 10 1 票 2 票 1 号（1<2 票）
0 号 15 2 票（最近被投的） 2 票 0 号（2==2）（最近被投的）
0 号 20 3 票 2 票 0 号（3>2）
1 号 25 3 票 3 票（最近被投的） 1 号 (3==3)（最近被投的）
0 号 30 4 票 3 票 0 号 (4>3)

我们可以在初始化的时候进行预处理，构造一个某个时间段领先的候选人的表。如下

时间 领先的候选人
0 0
5 1
10 1
15 0
20 0
25 1
30 0

如果给定一个时间t我们只需要找到比t小的最大的时间所对应的候选人是谁。

如给定时间t=12找到比 12 小的中最大的是10，此时对应领先的1号。

如给定时间t=15找到比 15 小的中最大的是15（比 15<=15），此时对应领先的0号。

注意：题目给的 persons 的取值范围，不是仅仅两个人

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class TopVotedCandidate {
public:
    vector<int> tops;
    vector<int> times;

    TopVotedCandidate(vector<int>& persons, vector<int>& times) {
        unordered_map<int, int> voteCounts;
        voteCounts[-1] = -1;
        int top = -1;
        for (auto & p : persons) {
            voteCounts[p]++;
            if (voteCounts[p] >= voteCounts[top]) {
                top = p;
            }
            tops.emplace_back(top);
        }
        this->times = times;
    }

    int q(int t) {
        // 找出比目标元素大的第一个元素
        int pos = upper_bound(times.begin(), times.end(), t) - times.begin() - 1;
        return tops[pos];
    }
};

tops就是我们所构造的表。

备注：

unordered_map:

简介

  1. unordered_map 是一个将 key 和 value 关联起来的容器，它可以高效的根据单个 key 值查找对应的 value。
  2. key 值应该是唯一的，key 和 value 的数据类型可以不相同。
  3. unordered_map 存储元素时是没有顺序的，只是根据 key 的哈希值，将元素存在指定位置，所以根据 key 查找单个 value 时非常高效，平均可以在常数时间内完成。
  4. unordered_map 查询单个 key 的时候效率比 map 高，但是要查询某一范围内的 key 值时比 map 效率低。
  5. 可以使用[]操作符来访问 key 值对应的 value 值。

map 与 unordered_map 的区别

  • 运行效率方面：unordered_map 最高，而 map 效率较低但 提供了稳定效率和有序的序列。
  • 占用内存方面：map 内存占用略低，unordered_map 内存占用略高，而且是线性成比例的。
  • map: #include < map >
  • unordered_map: #include < unordered_map >

成员函数

迭代器
方法 说明
begin 返回指向容器起始位置的迭代器（iterator）
end 返回指向容器末尾位置的迭代器
cbegin 返回指向容器起始位置的常迭代器（const_iterator）
cend 返回指向容器末尾位置的常迭代器
size 返回 unordered_map 支持的最大元素个数
empty 判断是否为空
operator[] 访问元素
at 访问元素
insert 插入元素
erase 删除元素
swap 交换内容
clear 清空内容
emplace 构造及插入一个元素
emplace_hint 按提示构造及插入一个元素
find 通过给定主键查找元素，没找到：返回 unordered_map::end
count 返回匹配给定主键的元素的个数
equal_range 返回值匹配给定搜索值的元素组成的范围
bucket_count 返回槽（Bucket）数
max_bucket_count 返回最大槽数
bucket_size 返回槽大小
bucket 返回元素所在槽的序号
load_factor 返回载入因子，即一个元素槽（Bucket）的最大元素数
max_load_factor 返回或设置最大载入因子
rehash 设置槽数
reserve 请求改变容器容量

upper_bound

简介

1
2
3
4
5

//查找 [first, last) 区域中第一个大于 val 的元素。
ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last,const T& val);

//查找 [first, last) 区域中第一个不符合 comp 规则的元素
ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last,const T& val, Compare comp);

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#include <iostream>     // std::cout
#include <algorithm>    // std::upper_bound
#include <vector>       // std::vector
using namespace std;
//以普通函数的方式定义查找规则
bool mycomp(int i, int j) { return i > j; }
//以函数对象的形式定义查找规则
class mycomp2 {
public:
    bool operator()(const int& i, const int& j) {
        return i > j;
    }
};
int main() {
    int a[5] = { 1,2,3,4,5 };
    //从 a 数组中找到第一个大于 3 的元素
    int *p = upper_bound(a, a + 5, 3);
    cout << "*p = " << *p << endl;
    vector<int> myvector{ 4,5,3,1,2 };
    //根据 mycomp2 规则，从 myvector 容器中找到第一个违背 mycomp2 规则的元素
    vector<int>::iterator iter = upper_bound(myvector.begin(), myvector.end(), 3, mycomp2());
    cout << "*iter = " << *iter;
    return 0;
}

结果

1
2

*p = 4
*iter = 1

#中等