leetcode315 计算右侧小于当前元素的个数
2024-09-06 06:14:03
1. 采用归并排序计算逆序数组对的方法来计算右侧更小的元素 time O(nlogn)；
计算逆序对可以采用两种思路：
a. 在左有序数组元素出列时计算右侧比该元素小的数字的数目为 cnt=r-mid-1; 右有序数组出列完成后cnt=end-mid;
b. 在右有序数组元素出列时计算左侧比该元素大的数字的数目为 cnt=mid-l+1; 左有序数组出列完成后cnt=0;
但是只有python 和java, 补充C++代码；
C++ code：
class Solution {
public:
void merge(vector<int>& nums, vector<int>& indexs,vector<int>& counts,int start, int mid, int end){
//在左有序数组出列时计算右有序数组中比当前数字小的
vector<int> tmps;//存储临时的index;
int l=start;
int r=mid+;
while(l<=mid && r<=end){
if(nums[indexs[l]]<=nums[indexs[r]]){
tmps.push_back(indexs[l]);
counts[indexs[l]]+=r-mid-;
l++;
}else{
tmps.push_back(indexs[r]);
r++;
}
}
while(l<=mid){
tmps.push_back(indexs[l]);
counts[indexs[l]]+=end-mid;
l++;
}
while(r<=end){
tmps.push_back(indexs[r]);
r++;
}
for(int i=;i<tmps.size();i++){
indexs[start+i]=tmps[i];
}
}
void mergesort(vector<int>& nums, vector<int>& indexs, vector<int>& counts,int start, int end){
if(start>=end) return;
int mid=start+(end-start)/;
mergesort(nums,indexs,counts,start,mid);
mergesort(nums,indexs,counts,mid+,end);
if(nums[indexs[mid]]>nums[indexs[mid+]])
merge(nums,indexs,counts,start,mid,end);
}
vector<int> countSmaller(vector<int>& nums) {
//归并排序计算 time nlogn
int len=nums.size();
vector<int> counts(len,);
vector<int> indexs(len,);
for(int i=;i<len;i++){
indexs[i]=i;
}
mergesort(nums,indexs,counts,,len-);
return counts;
}
};
可以采用一个全局的tmps临时数组而不是每次都中转；然后合并l<mid 与 (nums[indexs[l]]<=nums[indexs[r]])，简化代码如下：
class Solution {
public:
void merge(vector<int>& nums, vector<int>& indexs, vector<int>& counts, vector<int>& tmps, int start, int mid, int end){
int l=start;
int r=mid+;
for(int i=start;i<=end;i++){
if(r>end || ((l<=mid)&&(nums[indexs[l]]<=nums[indexs[r]]))){
tmps[i]=indexs[l];
counts[indexs[l]]+=r-mid-;
l++;
}else{
tmps[i]=indexs[r++];
}
}
for(int i=start;i<=end;i++){
indexs[i]=tmps[i];
}
}
void mergesort(vector<int>& nums, vector<int>& indexs, vector<int>& counts, vector<int>& tmps, int start, int end){
if(start>=end) return;
int mid=start+(end-start)/;
mergesort(nums,indexs,counts,tmps,start,mid);
mergesort(nums,indexs,counts,tmps,mid+,end);
merge(nums,indexs,counts,tmps,start,mid,end);
}
vector<int> countSmaller(vector<int>& nums) {
//可以借鉴利用归并排序统计逆序对数，
int len=nums.size();
if(len==) return {};
vector<int> indexs,counts,tmps;
for(int i=;i<len;i++){
indexs.push_back(i),counts.push_back(),tmps.push_back();
}
mergesort(nums,indexs,counts,tmps,,len-);
return counts;
}
};
2. 对O(n2)的暴力搜索进行改进：
倒序遍历，用一个数组sorted_nums记录当前元素右边的元素排序后的结果，每次用二分查找寻找新元素插入位置，并且得到right为counts的结果；
time O(n（n+logn）)但是要比归并排序慢十倍，是因为vector插入元素的关系？
C++ code：
class Solution {
public:
vector<int> countSmaller(vector<int>& nums) {
//暴力搜索，但是是从末尾计算，且将计算过的数排序存储，便于使用二分查找；
vector<int> sorted_nums, res;
for(int i=nums.size()-;i>=;i--){
int left=;
int right=sorted_nums.size();//这样mid索引不会出界，因为mid总是小于sorted_nums的长度的
//寻找nums[i]插入的位置，即比nums[i]大得第一个元素的位置；
while(left<right){
int mid=left+(right-left)/;
if(sorted_nums[mid]>=nums[i]){
right=mid;
}else{
left=mid+;
}
}
res.push_back(right);
sorted_nums.insert(sorted_nums.begin()+right,nums[i]);
}
reverse(res.begin(),res.end());
return res;
}
};
基本翻译
abbr. 号码（number）；数字（numeral）
n. (Num)人名；(柬)农
最新文章
- Laravel 5.3 auth中间件底层实现详解
- Java开源BI系统介绍(转）
- elf文件中的.plt .rel.dyn .rel.plt .got .got.plt的关系
- 《DSP using MATLAB》示例Example4.5
- LINUX系统下添加映射存储LUN
- 全面解析Linux数字文件权限
- EF Code First教程-03 数据库迁移Migrator
- java 读取excel文件（只读取xls文件）
- 利用 socket 发送 get/post 请求
- MongoDB面试题
- Ubuntu中安装 mercurial – TortoiseHG
- C# groupby 应用小技巧
- oracle使用数据泵进行数据的导入导出
- Python Tornado简介
- 14-hadoop-运行的2种方式
- JDK源码分析(五)——HashSet
- Wannafly挑战赛28 Solution
- netstat/lsof
- 【转载】Analysis Service Tabular Model #002 Analysis services 的结构:一种产品 两个模型
- ACE服务端编程4：ACE跨平台之运行时初始化和关闭