You are given an integer array nums and you have to return a new counts array. The countsarray has the property where counts[i]
is the number of smaller elements to the right of nums[i]
.
Example:
Input: [5,2,6,1]
Output:[2,1,1,0]
Explanation:
To the right of 5 there are 2 smaller elements (2 and 1).
To the right of 2 there is only 1 smaller element (1).
To the right of 6 there is 1 smaller element (1).
To the right of 1 there is 0 smaller element.
这道题给定了一个数组,让我们计算每个数字右边所有小于这个数字的个数,目测不能用 brute force,OJ 肯定不答应,那么为了提高运算效率,首先可以使用用二分搜索法,思路是将给定数组从最后一个开始,用二分法插入到一个新的数组,这样新数组就是有序的,那么此时该数字在新数组中的坐标就是原数组中其右边所有较小数字的个数,参见代码如下:
解法一:
// Binary Search
class Solution {
public:
vector<int> countSmaller(vector<int>& nums) {
vector<int> t, res(nums.size());
for (int i = nums.size() - ; i >= ; --i) {
int left = , right = t.size();
while (left < right) {
int mid = left + (right - left) / ;
if (t[mid] >= nums[i]) right = mid;
else left = mid + ;
}
res[i] = right;
t.insert(t.begin() + right, nums[i]);
}
return res;
}
};
上面使用二分搜索法是一种插入排序的做法,我们还可以用 C++ 中的 STL 的一些自带的函数,比如求距离 distance,或是求第一个不小于当前数字的函数 lower_bound(),这里利用这两个函数代替了上一种方法中的二分搜索的部分,两种方法的核心思想都是相同的,构造有序数组,找出新加进来的数组在有序数组中对应的位置存入结果中即可,参见代码如下:
解法二:
// Insert Sort
class Solution {
public:
vector<int> countSmaller(vector<int>& nums) {
vector<int> t, res(nums.size());
for (int i = nums.size() - ; i >= ; --i) {
int d = distance(t.begin(), lower_bound(t.begin(), t.end(), nums[i]));
res[i] = d;
t.insert(t.begin() + d, nums[i]);
}
return res;
}
};
// Binary Search Tree
class Solution {
public:
struct Node {
int val, smaller;
Node *left, *right;
Node(int v, int s) : val(v), smaller(s), left(NULL), right(NULL) {}
};
int insert(Node*& root, int val) {
if (!root) return (root = new Node(val, )), ;
if (root->val > val) return root->smaller++, insert(root->left, val);
return insert(root->right, val) + root->smaller + (root->val < val ? : );
}
vector<int> countSmaller(vector<int>& nums) {
vector<int> res(nums.size());
Node *root = NULL;
for (int i = nums.size() - ; i >= ; --i) {
res[i] = insert(root, nums[i]);
}
return res;
}
};
Github 同步地址:
https://github.com/grandyang/leetcode/issues/315
类似题目:
Queue Reconstruction by Height
参考资料:
https://leetcode.com/problems/count-of-smaller-numbers-after-self/