248-统计比给定整数小的数的个数
方法一（循环 + 二分查找）
首先对 A 排序，然后以 queries 的每个元素为 target ，用二分查找寻找 target 在 A 的下标，下标值即 A 中小于给定 target 的元素的数量
code
class Solution {
public:
/*
* @param A: An integer array
* @param queries: The query list
* @return: The number of element in the array that are smaller that the given integer
*/
vector<int> countOfSmallerNumber(vector<int> A, vector<int> queries) {
// write your code here
int sizeA = A.size(), sizeQ = queries.size();
if (sizeA <= 0 && sizeQ > 0) {
return vector<int>(sizeQ, 0);
}
if (sizeA <= 0 && sizeQ <= 0) {
return vector<int>();
}
vector<int> result;
sort(A.begin(), A.end());
for (int target : queries) {
int count = lower_bound(A.begin(), A.end(), target) - A.begin();
result.push_back(count);
}
return result;
}
};
方法二（线段树）
使用线段树，代码结果是 MLE（超出内存），不过还是简单介绍一下
使用线段树，线段树的额外属性 count 为 A 中 start 到 end 中小于 target 的元素个数，之后以 queries 的每个元素为 target，分别建立线段树
线段树自底而上构建，参考lintcode-439-线段树的构造 II
code
/**
* Definition of SegmentTreeNode:
*/
class mySegmentTreeNode {
public:
int start, end, count;
mySegmentTreeNode *left, *right;
mySegmentTreeNode(int start, int end, int max) {
this->start = start;
this->end = end;
this->count = count;
this->left = this->right = NULL;
}
};
class Solution {
public:
/*
* @param A: An integer array
* @param queries: The query list
* @return: The number of element in the array that are smaller that the given integer
*/
vector<int> countOfSmallerNumber(vector<int> A, vector<int> queries) {
// write your code here
int sizeA = A.size(), sizeQ = queries.size();
if (sizeA <= 0 && sizeQ > 0) {
return vector<int>(sizeQ, 0);
}
if (sizeA <= 0 && sizeQ <= 0) {
return vector<int>();
}
vector<int> result;
for (int target : queries) {
mySegmentTreeNode *root = build(0, sizeA - 1, A, target);
result.push_back(root->count);
}
return result;
}
mySegmentTreeNode * build(int start, int end, vector<int> &nums, int target) {
// write your code here
if (start > end) {
return nullptr;
}
mySegmentTreeNode *root = new mySegmentTreeNode(start, end, 0);
if (start != end) {
root->left = build(start, (start + end) / 2, nums, target);
root->right = build((start + end) / 2 + 1, end, nums, target);
root->count = root->left->count + root->right->count;
delete root->left; // 减小内存占用
delete root->right;
}
else {
if (target > nums[start]) {
root->count = 1;
}
else {
root->count = 0;
}
}
return root;
}
};