给定一个整型数组，int[] arr和一个布尔类型数组 boolean[] op，两个数组一定等长，假设长度为 N，arr[i] 表示客户编号，op[i] 表示客户操作
arr = [3, 3, 1, 2, 1, 2, 5 ...]
op = [T, T, T, T, F, T, F, ...]
依次表示：3用户购买了一件商品，3用户购买了一件商品，1用户购买了1件商品，2用户购买了一件商品，1用户退货了一件商品，2用户购买了一件商品，5用户退货了一件商品…
一对 arr[i] 和 op[i] 就代表一个事件：用户号为 arr[i]，op[i] == T 就代表这个用户购买了一件商品，op[i] == F 就代表这个用户退货了一件商品。
现在你作为电商平台负责人，你想在每一个事件到来的时候，都给购买次数最多的前 K 名用户颁奖。所以每个事件发生后，你都需要一个得奖名单（得奖区）。
得奖系统的规则：
如果某个用户购买商品数为 0 ，但是又发生了退货事件，则认为该事件无效，得奖名单和上一个事件发生后一致，如例子中的5用户
某用户发生购买商品事件，购买商品数+1；发生退货事件，购买商品数-1
每次都是最多K个用户得奖，K也为传入的参数
如果根据全部规则，得奖人数确实不够K个，那就以不够的情况输出结果。
得奖系统分为得奖区和候选区，任何用户只要购买数>0，一定在这两个区域中的一个
购买数最大的前 K 名用户进入得奖区，在最初时如果得奖区没有达到 K 个用户，那么新来的用户直接进入得奖区
如果购买数不足以进入得奖区的用户，进入候选区
如果候选区购买数最多的用户，已经足以进入得奖区，
该用户就会替换得奖区中购买数最少的用户（大于才能替换），
如果得奖区中购买数最少的用户有多个，就替换最早进入得奖区的用户
如果候选区中购买数最多的用户有多个，机会会给最早进入候选区的用户
候选区和得奖区是两套时间，
因用户只会在其中一个区域，所以只会有一个区域的时间，另一个没有；
从得奖区出来进入候选区的用户，得奖区时间删除，进入候选区的时间就是当前事件的时间（可以理解为 arr[i] 和 op[i] 中的 i)；
从候选区出来进入得奖区的用户，候选区时间删除，进入得奖区的时间就是当前事件的时间（可以理解为 arr[i] 和 op[i] 中的 i)；
如果某用户购买数 == 0，不管在哪个区域都离开，区域时间删除，离开是指彻底离开，哪个区域也不会找到该用户；如果下次该用户又发生购买行为，产生>0的购买数，会再次根据之前规则回到某个区域中，进入区域的时间重记。
请遍历 arr 数组和 op 数组，遍历每一步输出一个得奖名单
public List<List<Integer>> topK(int[] arr, boolean[] op, int k)
import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
public class Code02_EveryStepShowBoss {
public static class Customer { //用户
public int id; //用户id
public int buy; //买的商品数
public int enterTime; //进入得奖区或候选区的时间
public Customer(int v, int b, int o) {
id = v;
buy = b;
enterTime = 0;
}
}
public static class CandidateComparator implements Comparator<Customer> {
@Override
public int compare(Customer o1, Customer o2) {
//购买数多的排前面，如果一样，则谁早谁放前面
return o1.buy != o2.buy ? (o2.buy - o1.buy) : (o1.enterTime - o2.enterTime);
}
}
public static class DaddyComparator implements Comparator<Customer> {
@Override
public int compare(Customer o1, Customer o2) {
//购买数少的排前面，如果一样，则谁早谁放前面
return o1.buy != o2.buy ? (o1.buy - o2.buy) : (o1.enterTime - o2.enterTime);
}
}
//使用的加强堆的实现：https://maureen.blog.csdn.net/article/details/124952597?spm=1001.2014.3001.5502
public static class WhosYourDaddy {
private HashMap<Integer, Customer> customers;
private HeapGreater<Customer> candHeap;
private HeapGreater<Customer> daddyHeap;
private final int daddyLimit;
public WhosYourDaddy(int limit) {
customers = new HashMap<Integer, Customer>();
candHeap = new HeapGreater<>(new CandidateComparator());
daddyHeap = new HeapGreater<>(new DaddyComparator());
daddyLimit = limit;
}
// 当前处理i号事件，arr[i] -> id, buyOrRefund
public void operate(int time, int id, boolean buyOrRefund) {
if (!buyOrRefund && !customers.containsKey(id)) {
return;
}
if (!customers.containsKey(id)) {
customers.put(id, new Customer(id, 0, 0));
}
Customer c = customers.get(id);
if (buyOrRefund) {
c.buy++;
} else {
c.buy--;
}
if (c.buy == 0) {
customers.remove(id);
}
if (!candHeap.contains(c) && !daddyHeap.contains(c)) {
if (daddyHeap.size() < daddyLimit) {
c.enterTime = time;
daddyHeap.push(c);
} else {
c.enterTime = time;
candHeap.push(c);
}
} else if (candHeap.contains(c)) {
if (c.buy == 0) {
candHeap.remove(c);
} else {
candHeap.resign(c);
}
} else {
if (c.buy == 0) {
daddyHeap.remove(c);
} else {
daddyHeap.resign(c);
}
}
daddyMove(time);
}
public List<Integer> getDaddies() {
List<Customer> customers = daddyHeap.getAllElements();
List<Integer> ans = new ArrayList<>();
for (Customer c : customers) {
ans.add(c.id);
}
return ans;
}
private void daddyMove(int time) {
if (candHeap.isEmpty()) {
return;
}
if (daddyHeap.size() < daddyLimit) {
Customer p = candHeap.pop();
p.enterTime = time;
daddyHeap.push(p);
} else {
if (candHeap.peek().buy > daddyHeap.peek().buy) {
Customer oldDaddy = daddyHeap.pop();
Customer newDaddy = candHeap.pop();
oldDaddy.enterTime = time;
newDaddy.enterTime = time;
daddyHeap.push(newDaddy);
candHeap.push(oldDaddy);
}
}
}
}
public static List<List<Integer>> topK(int[] arr, boolean[] op, int k) {
List<List<Integer>> ans = new ArrayList<>();
WhosYourDaddy whoDaddies = new WhosYourDaddy(k);
for (int i = 0; i < arr.length; i++) {
whoDaddies.operate(i, arr[i], op[i]);
ans.add(whoDaddies.getDaddies());
}
return ans;
}
// 干完所有的事，模拟，不优化
//每一步都要返回一个长度为k的list
public static List<List<Integer>> compare(int[] arr, boolean[] op, int k) {
HashMap<Integer, Customer> map = new HashMap<>(); //id对应的实例
ArrayList<Customer> cands = new ArrayList<>(); //候选区
ArrayList<Customer> daddy = new ArrayList<>(); //得奖区
List<List<Integer>> ans = new ArrayList<>(); //每一步事件后的结果
for (int i = 0; i < arr.length; i++) {
int id = arr[i];
boolean buyOrRefund = op[i];
if (!buyOrRefund && !map.containsKey(id)) {//用户没买商品却发生了退货，忽略该事件
ans.add(getCurAns(daddy)); //保持上一步事件的答案
continue;
}
// 没有发生：用户购买数为0并且又退货了
// 用户之前购买数是0，此时买货事件
// 用户之前购买数>0， 此时买货
// 用户之前购买数>0, 此时退货
if (!map.containsKey(id)) {
map.put(id, new Customer(id, 0, 0)); //后面具体处理事件
}
// 买、卖
Customer c = map.get(id);
if (buyOrRefund) { //买
c.buy++;
} else { //卖
c.buy--;
}
if (c.buy == 0) { //购买数 = 0，两个区域都不能存在
map.remove(id);
}
// c
// 下面做
if (!cands.contains(c) && !daddy.contains(c)) { //新进来的用户且发生了购买
if (daddy.size() < k) { //得奖区人数 < k，直接放到得奖区
c.enterTime = i;
daddy.add(c);
} else { //否则放到候选区
c.enterTime = i;
cands.add(c);
}
}
//清除得奖区和候选区购买数为0的用户
cleanZeroBuy(cands);
cleanZeroBuy(daddy);
cands.sort(new CandidateComparator()); //候选区排序：从大到小
daddy.sort(new DaddyComparator()); //得奖区排序：从小到大
move(cands, daddy, k, i); //候选区的第一个和得奖区的第一个进行比较
ans.add(getCurAns(daddy));
}
return ans;
}
public static void move(ArrayList<Customer> cands, ArrayList<Customer> daddy, int k, int time) {
if (cands.isEmpty()) {
return;
}
// 候选区不为空
if (daddy.size() < k) { //得奖区的某个用户退货导致被移除，空出来了一个位置
Customer c = cands.get(0);
c.enterTime = time;
daddy.add(c);
cands.remove(0);
} else { // 得奖区满了，候选区有东西
if (cands.get(0).buy > daddy.get(0).buy) {
Customer oldDaddy = daddy.get(0);
daddy.remove(0);
Customer newDaddy = cands.get(0);
cands.remove(0);
newDaddy.enterTime = time;
oldDaddy.enterTime = time;
daddy.add(newDaddy);
cands.add(oldDaddy);
}
}
}
public static void cleanZeroBuy(ArrayList<Customer> arr) {
List<Customer> noZero = new ArrayList<Customer>();
for (Customer c : arr) {
if (c.buy != 0) {
noZero.add(c);
}
}
arr.clear();
for (Customer c : noZero) {
arr.add(c);
}
}
public static List<Integer> getCurAns(ArrayList<Customer> daddy) {
List<Integer> ans = new ArrayList<>();
for (Customer c : daddy) {
ans.add(c.id);
}
return ans;
}
// 为了测试
public static class Data {
public int[] arr;
public boolean[] op;
public Data(int[] a, boolean[] o) {
arr = a;
op = o;
}
}
// 为了测试
public static Data randomData(int maxValue, int maxLen) {
int len = (int) (Math.random() * maxLen) + 1;
int[] arr = new int[len];
boolean[] op = new boolean[len];
for (int i = 0; i < len; i++) {
arr[i] = (int) (Math.random() * maxValue);
op[i] = Math.random() < 0.5 ? true : false;
}
return new Data(arr, op);
}
// 为了测试
public static boolean sameAnswer(List<List<Integer>> ans1, List<List<Integer>> ans2) {
if (ans1.size() != ans2.size()) {
return false;
}
for (int i = 0; i < ans1.size(); i++) {
List<Integer> cur1 = ans1.get(i);
List<Integer> cur2 = ans2.get(i);
if (cur1.size() != cur2.size()) {
return false;
}
cur1.sort((a, b) -> a - b);
cur2.sort((a, b) -> a - b);
for (int j = 0; j < cur1.size(); j++) {
if (!cur1.get(j).equals(cur2.get(j))) {
return false;
}
}
}
return true;
}
public static void main(String[] args) {
int maxValue = 10;
int maxLen = 100;
int maxK = 6;
int testTimes = 100000;
System.out.println("测试开始");
for (int i = 0; i < testTimes; i++) {
Data testData = randomData(maxValue, maxLen);
int k = (int) (Math.random() * maxK) + 1;
int[] arr = testData.arr;
boolean[] op = testData.op;
List<List<Integer>> ans1 = topK(arr, op, k);
List<List<Integer>> ans2 = compare(arr, op, k);
if (!sameAnswer(ans1, ans2)) {
for (int j = 0; j < arr.length; j++) {
System.out.println(arr[j] + " , " + op[j]);
}
System.out.println(k);
System.out.println(ans1);
System.out.println(ans2);
System.out.println("出错了！");
break;
}
}
System.out.println("测试结束");
}
}
得奖区时间复杂度： O ( N ∗ l o g K ) O(N * logK) O(N∗logK)
候选区时间复杂度： O ( N ∗ l o g N ) O(N * logN) O(N∗logN)
每个事件到来要执行的复杂度： l o g N + l o g K + K logN + logK + K logN+logK+K 【候选区调整 + 得奖区调整 + 拉出一条链】
所以总的时间复杂度为： O ( N ∗ ( l o g N + l o g K + K ) ) O(N * (logN + logK + K)) O(N∗(logN+logK+K))
而暴力解法中每个事件到来都要进行排序，保守估计时间复杂度为 O ( N 2 ∗ l o g N ) O(N^2 * logN) O(N2∗logN)
/*************************************************************************
> File Name: 001.加强堆的应用.cpp
> Author:
> Mail:
> Created Time: Thu 19 May 2022 06:58:19 PM CST
************************************************************************/
#include <iostream>
#include <functional>
#include <unordered_map>
#include <vector>
#include <ctime>
#include <algorithm>
using namespace std;
/*
* 加强堆
*/
template <typename T>
class HeapGreater {
private:
typedef function<bool(T, T)> comparator; //function存储函数对象
vector<T> heap;
unordered_map<T, int> indexMap;
int heapSize;
comparator comp;
public:
HeapGreater(comparator c) {
heapSize = 0;
comp = c;
}
bool isEmpty() {
return heapSize == 0;
}
int size() {
return heapSize;
}
bool containsKey(T &obj) {
//return indexMap.find(obj) != indexMap.end();
return indexMap.count(obj);
}
T top() {
return heap[0];
}
void heapInsert(int index) {
while (comp(heap[index], heap[(index - 1) / 2])) {
swap(index, (index - 1) / 2);
index = (index - 1) / 2;
}
}
void push(T &obj) {
heap.push_back(obj);
indexMap[obj] = heapSize;
heapInsert(heapSize++);
}
T pop() {
T ans = heap[0];
swap(0, heapSize - 1);
indexMap.erase(ans);
heap.pop_back();
--heapSize;
heapify(0);
return ans;
}
void remove(T &obj) {
T replace = heap[heapSize - 1];
int index = indexMap[obj];
indexMap.erase(obj);
heap.pop_back();
--heapSize;
if (obj != replace) { //两个对象比较大小，自定义类型必须重载该运算符
heap[index] = replace;
indexMap[replace] = index;
resign(replace);
}
}
void resign(T &obj) {
int ind = indexMap[obj];
heap[ind] = obj;
heapInsert(indexMap[obj]);
heapify(indexMap[obj]);
}
vector<T> getAllElements() {
vector<T> ans;
for (T c : heap) {
ans.push_back(c);
}
return ans;
}
void heapify(int index) {
int left = index * 2 + 1;
while (left < heapSize) {
int best = left + 1 < heapSize && comp(heap[left + 1], heap[left]) ? left + 1 : left;
best = comp(heap[best], heap[index]) ? best : index;
if (best == index)
break;
swap(best, index);
index = best;
left = index * 2 + 1;
}
}
void swap(int i, int j) {
T o1 = heap[i];
T o2 = heap[j];
heap[i] = o2;
heap[j] = o1;
indexMap[o2] = i;
indexMap[o1] = j;
}
T get(int ind) {
return heap[ind];
}
};
class Customer {
public:
int id;
int buyCnt;
int enterTime;
public:
Customer() { }
Customer(int i, int c, int e) : id(i), buyCnt(c), enterTime(e) { }
bool operator==(const Customer &c) const {
return id == c.id;
}
bool operator!=(const Customer &c) const {
return id != c.id;
}
};
/*
* Customer的哈希函数
*/
namespace std {
template <>
class hash<Customer> {
public:
size_t operator()(const Customer &c) const {
int hashCode = hash<int>()(c.id);
return hashCode;
}
};
};
/*
* 候选区比较方式：
* 如果购买数量不等，按照数量从大到小排序；
* 若购买数量相等，按照进入时间从早到晚排序
*/
struct CandidateCompare {
bool operator()(const Customer &c1, const Customer &c2) const {
return c1.buyCnt != c2.buyCnt ? (c1.buyCnt > c2.buyCnt) : (c1.enterTime < c2.enterTime);
}
};
/*
* 得奖区比较方式：
* 若购买数量不等，按照数量从小到大排序；
* 若购买数量相等，按照进入时间从早到晚排序
*/
struct WinnerCompare {
bool operator()(const Customer &c1, const Customer &c2) const {
return c1.buyCnt != c2.buyCnt ? (c1.buyCnt < c2.buyCnt) : (c1.enterTime < c2.enterTime);
}
};
class WhosTheWinners {
private:
unordered_map<int, Customer> customers;
HeapGreater<Customer> *candidateHeap;
HeapGreater<Customer> *winnerHeap;
int winnerLimit;
public:
WhosTheWinners(int limit) : winnerLimit(limit) {
winnerHeap = new HeapGreater<Customer>(WinnerCompare());
candidateHeap = new HeapGreater<Customer>(CandidateCompare());
}
vector<int> getWinners() {
vector<Customer> winners = winnerHeap->getAllElements();
vector<int> ans;
for (Customer c : winners) {
ans.push_back(c.id);
}
return ans;
}
void operate(int time, int id, bool buyOrRefund) {
if (!customers.count(id) && !buyOrRefund)
return ;
if (!customers.count(id)) {
customers[id] = Customer(id, 0, 0);
}
Customer &c = customers[id]; //注意这个地方，一定要用&，不然后续buyCnt修改的值不会被修改到customers中
//cout << "c from customers : c.id = " << c.id << ", c.buyCnt = " << c.buyCnt << ", c.enterTime = " << c.enterTime << endl;
if (buyOrRefund) {
c.buyCnt++;
} else {
c.buyCnt--;
}
if (c.buyCnt == 0) {
customers.erase(id);
}
//注意使用自定义类型作为哈希表的key时，一定要做的两点：（1）实现哈希函数，以获得自定类型的哈希值 （2）自定义类中实现operator==，以判断两个对象是否相等
if (!candidateHeap->containsKey(c) && !winnerHeap->containsKey(c)) {
if (winnerHeap->size() < winnerLimit) {
c.enterTime = time;
winnerHeap->push(c);
} else {
c.enterTime = time;
candidateHeap->push(c);
}
} else if (candidateHeap->containsKey(c)) {
if (c.buyCnt == 0) {
candidateHeap->remove(c);
} else {
candidateHeap->resign(c);
}
} else {
if (c.buyCnt == 0) {
winnerHeap->remove(c);
} else {
winnerHeap->resign(c);
}
}
winnerMove(time, customers);
/*cout << "after : c from customers : c.id = " << c.id << ", c.buyCnt = " << c.buyCnt << ", c.enterTime = " << c.enterTime << endl;
//打印候选区的用户信息
cout << ">>Candidate Info:" << endl;
cout << "candidateHeap->size() = " << candidateHeap->size() << endl;
cout << "candidateHeap elements : " << endl;
for (int i = 0; i < candidateHeap->size(); i++) {
cout << "(" << candidateHeap->get(i).id << ", " << candidateHeap->get(i).buyCnt << ", " << candidateHeap->get(i).enterTime << ")" << endl;
}
cout << "<<==============" << endl;
cout << ">>Winner Info : " << endl;
cout << "winnerHeap->size() = " << winnerHeap->size() << endl;
cout << "winnerHeap elements : " << endl;
for (int i = 0; i < winnerHeap->size(); i++) {
cout << "(" << winnerHeap->get(i).id << ", " << winnerHeap->get(i).buyCnt << ", " << winnerHeap->get(i).enterTime << ")" << endl;
}
cout << "<<<<!!!!!!!!!!!!!!!" << endl;*/
}
void winnerMove(int time, unordered_map<int, Customer> &customers) {
if (candidateHeap->isEmpty())
return;
if (winnerHeap->size() < winnerLimit) {
Customer p = candidateHeap->pop();
p.enterTime = time;
winnerHeap->push(p);
customers[p.id].enterTime = time;
} else {
if (candidateHeap->top().buyCnt > winnerHeap->top().buyCnt) {
Customer oldWinner = winnerHeap->pop();
Customer newWinner = candidateHeap->pop();
oldWinner.enterTime = time;
newWinner.enterTime = time;
winnerHeap->push(newWinner);
candidateHeap->push(oldWinner);
//切记要更新customers中用户的id对应的时间
customers[oldWinner.id].enterTime = time;
customers[newWinner.id].enterTime = time;
}
}
}
};
void print(vector<int> &arr);
vector<vector<int> > topK(vector<int> &arr, vector<bool> &op, int k) {
vector<vector<int> > ans;
WhosTheWinners *whosTheWinners = new WhosTheWinners(k);
for (int i = 0; i < arr.size(); i++) {
//cout << "=================" << endl;
//cout << "topK : " << "arr[" << i << "] = " << arr[i] << ", op[" << i << "] = "<< op[i] <<endl;
whosTheWinners->operate(i, arr[i], op[i]);
ans.push_back(whosTheWinners->getWinners());
//print(ans[i]);
}
return ans;
}
//For test
void compareAndMove(unordered_map<int, Customer> &customers, vector<Customer> &cands, vector<Customer> &winners, int k, int time) {
if (cands.empty()) return ;
if (winners.size() < k) {
Customer c = cands[0];
c.enterTime = time;
winners.push_back(c);
cands.erase(cands.begin());
customers[c.id].enterTime = time;
} else {
if (cands[0].buyCnt > winners[0].buyCnt) {
Customer oldWinner = winners[0];
Customer newWinner = cands[0];
winners.erase(winners.begin());
cands.erase(cands.begin());
newWinner.enterTime = time;
oldWinner.enterTime = time;
winners.push_back(newWinner);
cands.push_back(oldWinner);
customers[oldWinner.id].enterTime = time;
customers[newWinner.id].enterTime = time;
}
}
}
void cleanZeroBuy(int id, vector<Customer> &arr) {
vector<Customer> noZero;
for (Customer &c : arr) {
if (c.id == id) {
c.buyCnt = 0;
}
if (c.buyCnt != 0) {
noZero.push_back(c);
}
}
arr.clear();
for (Customer c : noZero) {
arr.push_back(c);
}
}
void resignBuy(vector<Customer> &arr, int id, int buyCnt) {
for (Customer &c : arr) {
if (c.id == id) {
c.buyCnt = buyCnt;
}
}
}
vector<int> getCurAns(vector<Customer> &winners) {
vector<int> ans;
for (Customer &c : winners) {
ans.push_back(c.id);
}
return ans;
}
vector<vector<int> > compare(vector<int> &arr, vector<bool> op, int k) {
unordered_map<int, Customer> customers;
vector<Customer> cands;
vector<Customer> winners;
vector<vector<int> > ans;
for (int i = 0; i < arr.size(); i++) {
int id = arr[i];
//cout << "=======================" << endl;
//cout << "compare : id = " << id << ", op[" << i << "] = " << op[i] << endl;
bool buyOrRefund = op[i];
if (!buyOrRefund && !customers.count(id)) {
ans.push_back(getCurAns(winners));
continue;
}
if (!customers.count(id)) {
customers[id] = Customer(id, 0, 0);
}
Customer &c = customers[id];
if (buyOrRefund) {
c.buyCnt++;
} else {
c.buyCnt--;
}
if (c.buyCnt == 0) {
customers.erase(id);
}
if (!count(cands.begin(), cands.end(), c) && !count(winners.begin(), winners.end(), c)) {
if (winners.size() < k) {
c.enterTime = i;
//Tips：更改c的相关属性时，并没有更改到winners中的对象，winners中保存的是c的备份
winners.push_back(c);
} else {
c.enterTime = i;
cands.push_back(c);
}
} else if (count(cands.begin(), cands.end(), c)) {
if (c.buyCnt == 0) {
cleanZeroBuy(c.id, cands);
} else {
resignBuy(cands, c.id, c.buyCnt);
}
} else {
if (c.buyCnt == 0) {
cleanZeroBuy(c.id, winners);
} else {
resignBuy(winners, c.id, c.buyCnt);
}
}
//候选区buyCnt 从大到小
//得奖区buyCnt 从小到大
sort(cands.begin(), cands.end(), CandidateCompare());
sort(winners.begin(), winners.end(), WinnerCompare());
compareAndMove(customers, cands, winners, k, i);
sort(cands.begin(), cands.end(), CandidateCompare());
sort(winners.begin(), winners.end(), WinnerCompare());
//打印候选区和得奖区的用户信息
/*cout << "!!!!!!Candidate info:" << endl;
for (Customer c : cands) {
cout << "(" << c.id << ", " << c.buyCnt << ", " << c.enterTime << ")" << endl;
}
cout << "!!!!!!!Winner info:" << endl;
for (Customer c : winners) {
cout << "(" << c.id << ", " << c.buyCnt << ", " << c.enterTime << ")" << endl;
}*/
ans.push_back(getCurAns(winners));
}
return ans;
}
//构造测试数据
class Data {
public:
vector<int> arr;
vector<bool> op;
Data(vector<int> &a, vector<bool> &o) {
arr = a;
op = o;
}
};
Data randomData(int maxValue, int maxLen) {
int len = (rand() % maxLen) + 1;
vector<int> arr(len);
vector<bool> op(len);
for (int i = 0; i < len; i++) {
arr[i] = rand() % maxValue;
op[i] = ((rand() % 101 / (double)101)) < 0.5 ? true : false;
}
return Data(arr, op);
}
bool cmp(int &a, int &b) {
return a < b;
}
//比较两种方法的答案是否一致
bool sameAnswer(vector<vector<int>> &ans1, vector<vector<int>> &ans2) {
if (ans1.size() != ans2.size()) return false;
for (int i = 0; i < ans1.size(); i++) {
vector<int> cur1 = ans1[i];
vector<int> cur2 = ans2[i];
if (cur1.size() != cur2.size()) return false;
sort(cur1.begin(), cur1.end(), cmp);
sort(cur2.begin(), cur2.end(), cmp);
for (int j = 0; j < cur1.size(); j++) {
if (cur1[j] != cur2[j]) return false;
}
}
return true;
}
void printArray(vector<vector<int>> &ans) {
for (int i = 0; i < ans.size(); i++) {
for (int j = 0; j < ans[i].size(); j++) {
cout << ans[i][j] << " ";
}
cout << endl;
}
}
void print(vector<int> &arr) {
for (int i = 0; i < arr.size(); i++) {
cout << arr[i] << " ";
}
cout << endl;
}
int main() {
srand(time(0));
int maxValue = 100;
int maxLen = 1000;
int maxK = 10;
int testTime = 100000;
cout << "测试开始" << endl;
for (int i = 0; i < testTime + 1; i++) {
Data testData = randomData(maxValue, maxLen);
int k = (rand() % maxK) + 1;
vector<int> arr = testData.arr;
vector<bool> op = testData.op;
vector<vector<int>> ans1 = topK(arr, op, k);
vector<vector<int>> ans2 = compare(arr, op, k);
if (!sameAnswer(ans1, ans2)) {
for (int j = 0; j < arr.size(); j++) {
cout << endl << "[" << arr[j] << " , " << op[j] << ", " << j <<"]";
}
cout << endl;
cout << "k = " << k << endl;
cout << "ans1 : " << endl;
printArray(ans1);
cout << "ans2 : " << endl;
printArray(ans2);
cout << "出错了！" << endl;
break;
}
if (i && i % 100 == 0) cout << i << " cases passed!" << endl;
}
cout << "测试结束！" << endl;
return 0;
}
C++版和Java版的算法是一致的，但是有几个点需要注意：
HeapGreater中使用了自定义类型 Customer 作为 unordered_map 的 key 值，所以必须 (1）实现针对自定义类型的哈希函数 （2）在自定义类中实现 operator==；function 类型保存函数对象，此处是比较函数；id 相同的看做是同一个对象，其中的属性变化的时候也是在同一个对象中变化，所以实现针对 Customer 的哈希函数只能通过 id 来进行哈希，因为另外两个属性是变化的；id 是否相等来确定两个对象是否相同；compare 函数中的customers、cands 和 winners 是三个不同的空间，所以更改对象属性的时候一定要确保相同的对象属性变化是同步的，否则会导致很多错误；