首页 > 二叉树：二叉搜索树实现 逆序数问题

二叉树：二叉搜索树实现 逆序数问题

关于逆序数的问题描述如下：

已知数组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 
#include 
#include 
#include 
#include 
#include 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]

更多相关：

  • python文件关键行数_Python计算大文件行数方法及性能比较

    如何使用Python快速高效地统计出大文件的总行数, 下面是一些实现方法和性能的比较。1.readline读所有行使用readlines方法读取所有行:def readline_count(file_name):return len(open(file_name).readlines())2.依次读取每行依次读取文件每行内容进行计数:...

  • 2. 尾部的零

    题目 设计一个算法，计算出n阶乘中尾部零的个数 样例 11! = 39916800，因此应该返回 2   题解 一开始就用最简单对1-n找出5的个数，然后超时了。虽然都直到是要找5，因为2肯定比5多，所以5的个数就是0的个数，只是计算方法得简单明了。既然1-n里5的个数就是0，我们就看看规律。5 10 15 。。。n 那n/...

  • android EditText 限定中文个数与英文个数的解决方式

    EditText 限定中文8个英文16个的解决方法。 在EditText上控件提供的属性中有限定最大最小长度的方法。可是，对于输入时，限定中文8个英文16个时，怎么办？相当于一个中文的长度是两个英文的长度。 原理就不说了。自己看一下android的源代码。 以上直接上代码。 private final int maxLen =...

  • 172. Factorial Trailing Zeroes

    /**172. Factorial Trailing Zeroes *2016-6-4 by Mingyang* 首先别忘了什么是factorial，就是阶乘。那么很容易想到需要统计* (2,5)对的个数，因为2×5=10。但是这个条件放松一下就会发现其实只要数5的个数就好了，* 因为2实在是比5要多的多。那么这道题目就转...

  • java 读取excel_Java12POI操作Excel

            Apache POI是一个开源的利用Java读写Excel，WORD等微软OLE2组件文档的项目。        我的需求是对Excel的数据进行导入或将数据以Excel的形式导出。先上简单的测试代码：package com.xing.studyTest.poi;import java.io.FileInputSt...

  • C++ 生成随机数

    要取得[a,b)的随机整数，使用(rand() % (b-a))+ a; 要取得[a,b]的随机整数，使用(rand() % (b-a+1))+ a; 要取得(a,b]的随机整数，使用(rand() % (b-a))+ a + 1; 通用公式:a + rand() % n；其中的a是起始值，n是整数的范围。 要取得a到b之间的...

  • 基于C++的本征图像分解(Intrinsic Image Decomposition)

    利用本征图像分解(Intrinsic Image Decomposition)算法，将图像分解为shading(illumination) image 和 reflectance(albedo) image，计算图像的reflectance image。 Reflectance Image 是指在变化的光照条件下能够维持不变的图像部分...

  • 剑指offer：面试题39. 数组中出现次数超过一半的数字

    题目：面试题39. 数组中出现次数超过一半的数字 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。 你可以假设数组是非空的，并且给定的数组总是存在多数元素。 示例 1: 输入: [1, 2, 3, 2, 2, 2, 5, 4, 2] 输出: 2 限制： 1 <= 数组长度 <= 50000 解题： cl...

  • 剑指offer：面试题33. 二叉搜索树的后序遍历序列

    题目：二叉搜索树的后序遍历序列 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。 参考以下这颗二叉搜索树：      5     /    2   6   /  1   3示例 1： 输入: [1,6,3,2,5] 输出...

  • 二叉树：二叉搜索树的编码和解码

    二叉搜索树的编码和解码描述： 编码：即将一个二叉搜索树编码，节点数值转换为字符串 解码：即将一个字符串解码，数值转换为对应的二叉搜索树的节点 过程导图如下： 针对性编码实现如下: /*数字转字符串*/ void change_num_to_string(int val, string &tmp) {string buf;whil...

  • 二叉树：二叉搜索树的创建和插入

    二叉搜索树又名二叉排序树。 大概简略的思维导图如下，方便记忆特性 基本二叉搜索树创建过程如下 /*数据结构如下*/ typedef struct tree {int data;struct tree *left = NULL;struct tree *right = NULL; }Tree,*TreeNode;/*Node 为二...

  • Linux安装Nodejs

    Linux安装Nodejs 　　 　　　阿里云镜像： https://npm.taobao.org/mirrors/node/ 选择所需版本，进行下载。 　　　我这边下载的是：https://npm.taobao.org/mirrors/node/v8.2.1/node-v8.2.1-linux-x64.tar.gz  　　　 　　　...

  • Hadoop自学笔记（二）HDFS简单介绍

    1. HDFS Architecture 一种Master-Slave结构。包括Name Node, Secondary Name Node,Data Node Job Tracker, Task Tracker。JobTrackers: 控制全部的Task Trackers 。这两个Tracker将会在MapReduce课程里...

  • Sublime Text3配置Node.js开发环境

    下载Nodejs插件，下载zip压缩包后解压链接: http://pan.baidu.com/s/1hsBk60k 密码: jrcv打开Sublime Text3，点击菜单“首选项（N）” =>“浏览插件（B）”打开“Packages”文件夹，并将第1部的Nodejs文件夹剪切进来打开文件“Nodejs.sublime-build”，...

©2024 11GX.COM