二叉树：二叉搜索树实现 逆序数问题
关于逆序数的问题描述如下：
已知数组nums，求新数组count，count[i]代表了在nums[i]右侧且比 nums[i]小的元素个数。
例如:
nums = [5, 2, 6, 1], count = [2, 1, 1, 0];
nums = [6, 6, 6, 1, 1, 1], count = [3, 3, 3, 0, 0, 0];
nums = [5, -7, 9, 1, 3, 5, -2, 1], count = [5, 0, 5, 1, 2, 2, 0, 0];
这里我们使用二叉搜索树实现，可以思考如下：
将nums和count数组都进行逆序，则会有如下结果
nums=[1,-2,5,3,1,9,-7,5],count = [0,0,2,2,1,5,0,5]
此时我们发现，对于nums中的每个元素，只需要确定它的左侧比自己小的元素的个数，这样的结果就可以构造出右侧的count。
自然，我们想到了二叉搜索树的性质，可以画出如下导图：
代码实现如下（文末有完整测试代码）:
/*二叉树数据结构，新增count属性，保存左节点的个数*/
typedef struct tree
{int data;int count;//保存当前节点有多少个左节点struct tree *left;struct tree *right;tree(int x):data(x),left(NULL),right(NULL),count(0){}
}Tree,*TreeNode;/*通过二叉树进行计算*/
void insert(Tree *root, Tree *node, int &small_count) {if (node -> data <= root ->data) {root -> count ++; //当前节点左节点个数累加，因为插入的节点已经比当前节点小了if (root -> left) {insert(root->left,node, small_count);} else {root -> left = node;}} else {/*如果大于当前节点，则说明当前节点的所有左节点包括自己都比插入节点小，进行赋值*/small_count += root -> count + 1; if (root ->right) {insert(root ->right, node, small_count);} else {root -> right = node;}}
}/*获取最终的逆序数组*/
std::vector<int> get_smaller_numbers(std::vector<int> &arr) {std::vector<int> count; //逆序后的数组std::vector<Tree *> node; //二叉树节点数组std::vector<int> result; //最终逆序结果的数组Tree *tmp;for (int i = arr.size() - 1;i >= 0; i--) {node.push_back(new tree(arr[i]));}count.push_back(0);for (int i = 1;i < arr.size(); ++i) {int small_count = 0;insert(node[0],node[i],small_count);count.push_back(small_count);}/*对计算好的结果进行逆序，恢复初始结果*/for (int i = count.size() - 1; i >= 0; --i) {delete node[i];result.push_back(count[i]);}return result;
}
测试代码如下:
#include <iostream>
#include <stack>
#include <vector>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>using namespace std;
/*二叉树数据结构*/
typedef struct tree
{int data;int count;//保存当前节点有多少个左节点struct tree *left;struct tree *right;tree(int x):data(x),left(NULL),right(NULL),count(0){}
}Tree,*TreeNode;/*通过二叉树进行计算*/
void insert(Tree *root, Tree *node, int &small_count) {if (node -> data <= root ->data) {root -> count ++;if (root -> left) {insert(root->left,node, small_count);} else {root -> left = node;}} else {small_count += root -> count + 1;if (root ->right) {insert(root ->right, node, small_count);} else {root -> right = node;}}
}std::vector<int> get_smaller_numbers(std::vector<int> &arr) {std::vector<int> count; //逆序后的数组std::vector<Tree *> node; //二叉树节点数组std::vector<int> result; //最终逆序结果的数组Tree *tmp;for (int i = arr.size() - 1;i >= 0; i--) {node.push_back(new tree(arr[i]));}count.push_back(0);for (int i = 1;i < arr.size(); ++i) {int small_count = 0;insert(node[0],node[i],small_count);count.push_back(small_count);}/*对计算好的结果进行逆序，恢复初始结果*/for (int i = count.size() - 1; i >= 0; --i) {delete node[i];result.push_back(count[i]);}return result;
}int main(int argc, char const *argv[])
{int test[] = {5,-7,9,1,3,5,-2,1};std::vector<int> num;for (int i = 0;i < 8; ++i) {num.push_back(test[i]);}std::vector<int> result;result = get_smaller_numbers(num);for (int i = 0;i < result.size(); ++i) {cout << "[" << result[i] << "] ";}return 0;
}
输出结果如下:
[5] [0] [5] [1] [2] [2] [0] [0]
相关文章：
C语言文件实验要求,实验教学的目的和要求.doc
实验教学的目的和要求实验教学的目的和要求：通过实验，让学生全面掌握高级语言程序设计的思想与方法，掌握C语言的特点，C语言的语法规则，C语言的数据类型、表达式及控制流程；通过编程，提高程序设计…
这些工作的日子
已经毕业10个月了，工作了9个月，想说我是个刚毕业的大学僧，没有遇到什么社会上的勾心斗角，没有遇到天大的难题，没有看到那种大起大落的景象，一切还是那样平平淡淡的，当看见附近大学的大学僧的时候…
python基础类型
range：生成指定范围内的数字，只在python2中使用，python3中没有此用法 例：生成0-30内的偶数 转载于:https://www.cnblogs.com/gaoyuxia/p/10239421.html
linux系统目录树/内核源码目录树
关于系统目录树和源码目录树的结构图如下 内核版本: centos 7.0 升级内核之后 3.10.0-957-5.1.e17
顺时针打印二维数组C语言递归,按顺时针打印矩阵
存在二种解题思路: 一种是递归解法,一种是层层递进解法图解递归解法如图所示, 一个5*5的矩阵先打印最外层的圈, 然后剩余最里层3*3的矩阵, 如图.将3*3的矩阵继续打印最外层,思路与打印最外层思路一样,我们就可以考虑使用递归实现.最后只剩余一个元素,也可以看成一个矩阵,不过不…
降低噪声和电磁干扰的原则
1.尽量采用45折线转载于:https://www.cnblogs.com/asulove/p/3827246.html
翻译：java.util.regex.Pattern
java.util.regex.PatternA compiled representation of a regular expression. A regular expression（正则表达式）, specified as a string, must first be compiled into an instance of this class（首先编译成Pattern对象）. The…
学习笔记53—Wilcoxon检验和Mann-whitney检验的区别
Wilcoxon signed-rank test应用于两个related samples Mann–Whitney U test也叫Wilcoxon rank-sum test，应用于两个independent samples的情samples size小的时候，是有列表的，sample size大到20左右时，就可以使用正态分布来近似…
s-systemtap工具使用图谱（持续更新）
整体的学习思维导图如下，后续持续更新完善 文章目录安装简介执行流程执行方式stap脚本语法探针语法API函数探针举例变量使用基本应用1. 定位函数位置2. 查看文件能够添加探针的位置3. 打印函数参数（结构体）4. 打印函数局部变量5. 修改函数局…
2014 Super Training #8 C An Easy Game --DP
原题：ZOJ 3791 http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode3791 题意：给定两个0-1序列s1, s2，操作t次，每次改变m个位置，求把s1改变为s2的方法总数。解法： DP，s1和s2哪些位置…
qq分享组件 android,移动端，分享插件
移动端，分享插件发布时间：2018-06-26 10:03,浏览次数：762最近有一个活动页需要在移动端浏览器分享网页到微信，QQ。虽然每一个浏览器都有分享到微信的能力，但不是每个都提供接口供网页来调用。及时有提供，浏…
MySQL中更改表操作
2019独角兽企业重金招聘Python工程师标准>>> 添加一列： alter table t_stu add tel char(20); 删除一个列： alter table t_stu drop column tel; 添加唯一约束： alter table t_stu add constraint uk_srname unique(scode); 添加主…
Maven-环境配置
二更 可算搞好了，除了下面外，我找到了setting.xml里面的东西，给出来就好了，简单就是mvn -v弄好后，setting.xml里面写好的话，直接加入，然后让eclipse下载jar包 然后就可以运行网上的基本项目了 1…
分布式存储(ceph)技能图谱（持续更新）
一下为个人结合其他人对分布式存储 所需的技能进行总结，绘制成如下图谱，方便针对性学习。 这里对分布式存储系统接触较多的是ceph,所以在分布式存储系统分支上偏向ceph的学习。 如有分类有问题或者分支不合理，欢迎大家批评指正，目…
android如何查看方法属于哪个类,Android Studio查看类中所有方法和属性
css-关于位置当你设置一个你想要相对的模块为relative 你这个模块为absolute 则你的这个absolute会相对relative的那个模块进行移动.微信公众平台自动回复wechatlib.jar的生成及wechatlib解析微信公众平台出来有一段时日了,官方提供的自动回复的接口调用大致是这么些…
读javascript高级程序设计03-函数表达式、闭包、私有变量
一、函数声明和函数表达式 定义函数有两种方式：函数声明和函数表达式。它们之间一个重要的区别是函数提升。 1.函数声明会进行函数提升，所以函数调用在函数声明之前也不会报错： test(); function test(){ alert(1); } 2.函数表达式不会进行函…
集成公司内部的多个子系统（兼容B/S和C/S），实现单点登录功能的多系统的统一入口功能...
有一句话也挺有意思的，一直在模仿但从未超越过，文章里的技术也都是相对简单的技术，但是实实在在能解决问题，提高效率。现在人都懒得瞎折腾，能多简单就多简单，谁都不希望总是做一些重复的工作，我…
mysql无法远程连接
在mysql的mysql数据库下： select user,host from user;(查看，没有本机的访问权限) grant all privileges on *.* to root"xxx.xxx.xxx.xxx" identified by "密码";(xx为本机ip,%为所有IP) flush privileges; select user,host from …
哈希表的分类，创建，查找 以及相关问题解决
总体的hash学习导图如下： 文章目录定义分类字符hash排序hash链式hash（解决hash冲突）创建链式hash查找指定数值STL map(hash)哈希分类 完整测试代码应用（常见题目）1. 回文字符串（Longest Palindrome&#x…
android 自定义音乐圆形进度条,Android自定义View实现音频播放圆形进度条
本篇文章介绍自定义View配合属性动画来实现如下的效果实现思路如下：根据播放按钮的图片大小计算出圆形进度条的大小根据音频的时间长度计算出圆形进度条绘制的弧度通过Handler刷新界面来更新圆形进度条的进度具体实现过程分析：首先来看看自定义View中定义…
jsp error-page没有生效
1、首页检查web.xml中的配置，确保路径是正确的 <error-page> <error-code>404</error-code> <location>/error.jsp</location> </error-page> 2、然后再检查error.jsp文件内容是否有问题，比如只有<head>&…
CTO（首席技术官）
CTO（首席技术官）英文Chief Technology Officer，即企业内负责技术的最高负责人。这个名称在1980年代从美国开始时兴。起于做很多研究的大公司，如General Electric，AT&T，ALCOA，主要责任是将科…
把数组排成最小的数
题目 输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。 思路 一 需要找到字典序最小的哪个排列…
shell脚本自动执行，top命令无输出
shell脚本在系统启动时推后台自动执行，发现其中/usr/bin/top -n 1 -c -b -u ceph 命令并无输出 但是系统启动之后手动执行脚本，&推后台脚本中的top仍然能够正常输出，仅仅是系统发生重启，该功能就不生效了 stackoverflow 推荐…
0709 C语言常见误区----------函数指针问题
1.函数指针的定义 对于函数 void test(int a, int b){ // } 其函数指针类型是void (* ) (int , int)， 注意这里第一个括号不能少， 定义一个函数指针，void (* pfunc)(int , int) ,其中pfunc就是函数指针类型， 它指向的函数类型必须…
android 定时换图片,android 视频和图片切换并进行自动轮播
刚入android没多久，遇到的比较郁闷的问题就是子线程主线程的问题，更改UI界面，本想做一个图片的轮播但是比较简单，然后就试试实现视频跟图片切换播放进行不停的循环播放。也用过不少控件，但是知其然不知其所以然&#x…
Win8:Snap 实现
Win8允许分屏的操作，所以我们必须让我们App能对Snap模式视图做出反应，这样也便于通过Store的审核。如果项目中在Snap展现的功能不大，我们可以仅用一张logo代替，类似系统的商店应用。 我的项目实现效果： 实现思路是在你…
ping命令使用及其常用参数
PING (Packet Internet Groper)，因特网包探索器，用于测试网络连接量检查网络是否连通，可以很好地帮助我们分析和判定网络故障。Ping发送一个ICMP(Internet Control Messages Protocol）即因特网信报控制协议；回声请求消…
g-gdb工具使用图谱(持续更新)
如下为整个GDB的学习导图
android bitmap 转drawable,android Drawable转换成Bitmap失败
错误代码：08-07 06:42:30.482 28497-28497/app.tianxiayou E/AndroidRuntime﹕ FATAL EXCEPTION: mainProcess: app.tianxiayou, PID: 28497java.lang.RuntimeException: Unable to start activity ComponentInfo{app.tianxiayou/app.tianxiayou.AppInfoActivity}: …