当前位置： 首页 > 编程日记 > 正文

递归/归并：count of smaller numbers求逆序数

编程日记 2024-04-19 20:30:00

已知数组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数组[5,2,6,1]中：
对于nums[0]=5，其后面比他小的元素有两个，则count[0]=2
对于nums[1]=2，其后面比她小的元素有一个，则count[1]=1
…

此时，一个比较普通但是时间复杂度较高（O(n^2)）的算法实现即为先排序，再一个一个元素遍历，构造count数组。

但是我们直到分治算法的过程时间复杂度为(O(nlogn))，那可不可以尝试一下使用归并的过程构建count数组。

分治算法的步骤：

  1. 分解，将要解决的问题划分成若 干规模较小的同类问题;
  2. 求解，当子问题划分得足够小时 ，用较简单的方法解决;
  3. 合并，按原问题的要求，将子问题 的解逐层合并构成原问题的解。

分解：
我们要构造count数组，假如这个数组 被分为两个有序的数组
nums: [-7 1 5 9],[-2 1 3 5]
假设：
nums1[-7 1 5 9]， 下标从i开始
nums2[-2 1 3 5]， 下标从j开始
进行合并两个有序链表的过程：
i =0, j= 0, nums[i] = -7时，count[i] = 0
num1[i] < nums2[j], i++
对于i=1,j=0,count[i] = 1

nums1[i] > nums2[j], j++
此时i=1,j=1,count[i] = 1

…

综合上面的过程，我们能够发现，对于count1[i] ，它总是等于同一时刻j的数值
即count[0] = 0, count[1] =1, count[2] = 3;

此时我们能够对以上逆序数组通过归并排序进行构造：

/*pair<int,int> first元素保存当前数组的值，second元素保存当前元素的下标*/void merge_two_arr(std::vector<pair<int,int>> &arr1, std::vector<pair<int,int>> &arr2, std::vector<pair<int,int>> &result,std::vector<int> &count) {int i = 0;int j = 0;while(i < arr1.size() && j < arr2.size()) {if (arr1[i].first <= arr2[j].first) { //归并的筛选条件/*对于此时的arr[i]的元素，它的count值为上一个j所代表的数值因为之前的arr2[j]以及比它小的元素肯定比当前的arr[i]小。*/count[arr1[i].second] += j; result.push_back(arr1[i]);i++;} else {result.push_back(arr2[j]);j++;}}if (i == arr1.size()) {for (;j < arr2.size(); ++j) {result.push_back(arr2[j]);}} else {//对于剩余的元素做同样的处理for (;i < arr1.size(); ++i) {count[arr1[i].second] += j;result.push_back(arr1[i]);}}
}

测试代码如下:

#include <iostream>
#include <vector>
#include <algorithm>using namespace std;/*
已知数组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];
*//**/
void merge_two_arr(std::vector<pair<int,int>> &arr1,std::vector<pair<int,int>> &arr2,std::vector<pair<int,int>> &result,std::vector<int> &count) {int i = 0;int j = 0;while(i < arr1.size() && j < arr2.size()) {if (arr1[i].first <= arr2[j].first) {count[arr1[i].second] += j;result.push_back(arr1[i]);i++;} else {result.push_back(arr2[j]);j++;}}if (i == arr1.size()) {for (;j < arr2.size(); ++j) {result.push_back(arr2[j]);}} else {for (;i < arr1.size(); ++i) {count[arr1[i].second] += j;result.push_back(arr1[i]);}}
}/*归并排序*/
void merge_sort(std::vector<pair<int,int>> &arr, std::vector<int> &count) {if (arr.size() < 2) {return ;}int mid = arr.size() / 2;std::vector<pair<int,int>> arr1;std::vector<pair<int,int>> arr2;for (int i = 0; i < mid; ++i) {arr1.push_back(arr[i]);}for (int i = mid; i< arr.size(); ++i){arr2.push_back(arr[i]);}/*分治*/merge_sort(arr1, count);merge_sort(arr2, count);arr.clear();/*求解*/merge_two_arr(arr1,arr2,arr,count);
}int main(int argc, char const *argv[])
{std::vector<pair<int,int>> arr;std::vector<int> count;int n;int tmp;cin >> n;for (int i = 0;i < n; ++i) {cin >> tmp;arr.push_back(make_pair(tmp,i));count.push_back(0);}merge_sort(arr, count);for (int i = 0;i < count.size(); ++i) {cout << count[i] << " ";}cout << endl;return 0;
}

最终输出如下:

#输入
8
5 -7 9 1 3 5 -2 1
#输出
5 0 5 1 2 2 0 0

https://www.dkcj.cn/info/4922.html

相关文章：

远程计划任务管理

有时你需要远程管理或运行一批机器&#xff0c;但是按要求你没有权限或者不能安装客户端&#xff0c;下面的批处理可能帮上你的忙&#xff0c;将下方代码保存为批处理&#xff0c;并创建Clients.txt&#xff0c;存放的是以回车分隔的IP echo off setlocal enabledelayedexpansi…

编程日记2024/04/19 20:00:00

linux shell for 循环变量,shell for循环总结

1 shell for循环语法for 变量 in 列表docommand1command2...commandNdone1.1 读取列表中的值#!/bin/bashfor test in apple boy cat dogdoecho The next state is $testdone结果&#xff1a;The next state is appleThe next state is boyThe next state is catThe next state …

编程日记2024/04/19 19:30:00

自定义堆栈（回文检测）

using System; using System.Collections;namespace CStack {class Program{static void Main(string[] args){CStack alist new CStack();string ch;string word "上海自来水来自海上";bool isPalindrome true;for (int x 0; x < word.Length; x){alist.Push…

编程日记2024/04/19 19:00:00

二叉树(C++)：创建，前中后序遍历（递归+非递归），获取叶子节点个数，获取树的高度

文章目录前言创建二叉树先序遍历中序遍历后序遍历获取叶子节点个数获取树的高度测试代码前言 现有如下二叉树: 关于二叉树的相关操作&#xff0c;我们能够发现二叉树从根节点到子节点&#xff0c;以及每个中间节点基本都能够拆分为若干个子节点的操作&#xff0c;且每个子节点…

编程日记2024/04/19 18:30:00

6月11号=》121页-125页

6.1　　样式单概述 W3C已经给出了两种样式单语言的推荐标准&#xff0c;一种是级联样式单CSS(Cascading Style Sheets)&#xff0c; 另一种是可扩展样式单语言XSL(eXtensible Stylesheet Language)。 6.1.1　　CSS CSS主要提供如下两个功能&#xff1a; 1&#xff1a;对页面的字…

编程日记2024/04/19 18:00:00

linux cp sync,通过SSH使用Rsync传输文件，复制和同步文件及目录

在本文中&#xff0c;我们将解释如何通过SSH使用rsync复制文件。当涉及在网络上的系统之间传输文件时&#xff0c;Linux和Unix用户可以使用许多工具&#xff0c;最流行的数据传输协议是SSH和FTP&#xff0c;虽然FTP很受欢迎&#xff0c;但总是喜欢使用SSH&#xff0c;因为它是传…

编程日记2024/04/19 17:30:00

【Java笔记】C++与Java的对比

接口&#xff1a; C可以多重继承&#xff0c;而Java不可以。但是Java里一个类可以声明实现多个接口。

编程日记2024/04/19 17:00:00

cf792b循环链表

头尾链接一下就好&#xff0c; /* 1 2 3 4 5 6 7:4 5 6 7 1 2 3:2 3 5 6 7 1:5 6 7 1 3:6 7 1 3:1 3 7 */ #include<bits/stdc.h> using namespace std; int main(){int n,k,q[200],nxt[200],p,pre,tot;scanf("%d%d",&n,&k);for(int i1;i&…

编程日记2024/04/19 16:30:00

二叉树：路径之和 Path Sum

给定一个二叉树与整数sum&#xff0c;找出所有从根节点到叶结点的路径&#xff0c;这些路 径上的节点值累加和为sum 即创建一个二叉树&#xff0c;要求二叉树中有一个路径从根节点到叶节点到路径加起来代表到和为 给定的sum 如下二叉树 给定路径之和为18&#xff0c;则需要输…

编程日记2024/04/19 16:00:00

从零开始编写自己的C#框架（16）——Web层后端父类

从零开始编写自己的C#框架&#xff08;16&#xff09;——Web层后端父类 原文:从零开始编写自己的C#框架&#xff08;16&#xff09;——Web层后端父类 本章节讲述的各个类是后端系统的核心之一&#xff0c;涉及到系统安全验证、操作日志记录、页面与按键权限控制、后端页面功能…

编程日记2024/04/19 15:30:00

c语言中的普通字符包括什么,【判断题】C语言中的字符常量通常有两种形式:普通字符和转义字符。...

【判断题】C语言中的字符常量通常有两种形式:普通字符和转义字符。更多相关问题&#xff0d;&#xff0d;&#xff0d;Can you speak French&#xff1f;&#xff0d;&#xff0d;&#xff0d;Yes, but only____.A&#xff0e;a littleB&#xff0e;littleC&#xff0e;muchD&a…

编程日记2024/04/19 15:00:00

Codeforces Round #104 (Div. 2) E DP(01背包模型) +组和+除法取模求逆元

题意&#xff1a; 规定只包含4或7的数为幸运数字&#xff0c;给定n个数的序列&#xff0c;求他的子序列&#xff0c;使得该子序列的长度为k并且满足该子序列中不存在相同的两个幸运数字。问一共寻在多少种可能。&#xff08;只要该数的下标不同则认为是不同的序列&#xff09; …

编程日记2024/04/19 14:30:00

django 增加验证邮箱功能

在user文件夹下新建python包&#xff0c;utils 在包内新建文件email_send.py,其中包括验证字符串随机码的产生&#xff0c;数据库的存储和email的发送 # -*- coding: utf-8 -*- # 作者&#xff1a;神秘藏宝室 # 日期&#xff1a;2019/1/1 22:21 from random import Random from…

编程日记2024/04/19 14:00:00

二叉树：最近的公共祖先 Lowest Common Ancestor of a Binary Tree

已知二叉树&#xff0c;求二叉树中给定的两个节点的最近公共祖先。 最近公共祖先: 两节点v与w的最近公共祖先u&#xff0c;满足在树上最低(离根最 远)&#xff0c;且v,w两个节点都是u的子孙。 如上二叉树&#xff0c;6和8号节点的公共祖先有4&#xff0c;1&#xff1b;但是最近…

编程日记2024/04/19 13:30:00

VS不显示最近打开的项目

VS2012不显示最近打开的项目 解决方法&#xff0c; 在"运行"中输入 " gpedit.msc"打开后在"用户配置"-"管理模板"-"任务栏和开始菜单" 然后将用户配置-->管理模板-->不保留最近打开文档的历史 将此选项设置为禁用 源…

编程日记2024/04/19 13:00:00

河科大c语言上机实验答案,2016年河南科技学院信息工程学院C语言上机编程考研复试题库...

一、选择题1&#xff0e; 以下选项中&#xff0c;能用作数据常量的是( )。答:D【解析】A 项错误&#xff0c;十六进制数用数学0和字符x (或大写字母X )开头&#xff1b;B 项错误&#xff0c;八进制整数常量以数字0开始&#xff0c;有效数字为0〜7; C项错误&#xff0c;C 语言中…

编程日记2024/04/19 12:30:00

无符号数溢出之后

2019独角兽企业重金招聘Python工程师标准>>> [rootcentos ~]# cat test.c #include <stdio.h>int main() {unsigned short i 0x0;while(1){printf("%u \n",i);if(i 0) //溢出之后 又会回到 0 所以不会 死循环break;} } 转载于:https://my.oschin…

编程日记2024/04/19 12:00:00

加载BeanFactory

前言 上一篇文章讲述了ApplicationContext扩展功能的之一&#xff1a;环境准备。这篇文章接着讲述ApplicationContext的扩展功能-----加载BeanFactory&#xff0c;也就是初始化BeanFactory&#xff0c;并进行XML文件的读取。 加载BeanFactory obtainFreshBeanFactory方法从字面…

编程日记2024/04/19 11:30:00

t-top 命令详解

前言 展示操作系统进程信息。动态得&#xff0c;实时得展示正在运行的操作系统进程信息。 所显示的系统摘要信息的类型以及为进程显示的信息的类型&#xff0c;顺序和大小都是用户可配置的&#xff0c;并且可以使配置在重新启动后保持不变。该程序为流程操作提供了一个有限的交…

编程日记2024/04/19 11:00:00

怎么看懂c语言程序,求讲解一下这个程序，我看了1个小时都没有看懂，

该楼层疑似违规已被系统折叠 隐藏此楼查看此楼# include #define N 9void fun(int a[], int n){ int i,j, max, min, px, pn, t;for (i0; i{/**********found**********/max min ___a[i]__;px pn i;for (ji1; j/**********found**********/if (max<___a>{ max a[j];…

编程日记2024/04/19 10:30:00

【转】Winform输入法控制

来源&#xff1a;http://blog.itpub.net/23109131/viewspace-630576 想实现输入法切换&#xff1a;思路&#xff0c;找出当前系统所有输入法总个数&#xff0c;当前输入法在总输入法中的索引&#xff0c;通过改变索引值&#xff0c;来切换输入法 void input() {//变全角为半角的…

编程日记2024/04/19 10:00:00

vector与结构体联合使用 在磁盘中生成.txt 文件

一下纯属个人总结、欢迎拍砖&#xff01;谢谢 我意思到以练促进学习C编程基础是很有帮助的 这篇文章是我为了熟悉掌握文件流和STL中的vector以及结构体三个只知识点所写的代码&#xff1a; #include <string> #include <stdlib.h> #include <iostream> #incl…

编程日记2024/04/19 09:30:00

SQL Server 2008 R2如何开启数据库的远程连接

SQL Server 2008 R2如何开启数据库的远程连接 转载于:https://www.cnblogs.com/macT/p/10213025.html

编程日记2024/04/19 09:00:00

二分法：二分查找（递归+非递归）实现

二分查找又称折半查找&#xff0c;首先&#xff0c;假设表中元素是按升序排列&#xff0c;将 表中间位置的关键字与查找关键字比较: 如果两者相等&#xff0c;则查找成功;否则利用中间位置将表分成前、后两个子表: 1)如果中间位置的关键字大于查找关键字&#xff0c;则进一步查…

编程日记2024/04/19 08:30:00

mongodb数据库的一些常用命令列表

超级用户相关&#xff1a;use admin#增加或修改用户密码db.addUser(ixigua,pwd)#查看用户列表db.system.users.find()#用户认证db.auth(ixigua,pwd)#删除用户db.removeUser(mongodb)#查看所有用户show users#查看所有数据库show dbs#查看所有的collectionshow collections#查看…

编程日记2024/04/19 08:00:00

c语言函数库哪里keyk,[精品]C语言库函数(字母G-K)-教案.doc

[精品]C语言库函数(字母G-K)-教案C语言库函数(字母G-K)- -??????????????????????????????????????(G类字母) - 1函数名: gcvt 功 能: 把浮点数转换成字符串 用 法: char *gcvt(double value, int ndigit, char *buf); 程序例: #include…

编程日记2024/04/19 07:30:00

超链接调用js函数

<a href"javascript:gouwu()" ><span class"Buy" id"buyButton"></span></a>超链接调用js前面要加javascript:****************************SuppressWarningsJ2SE 提供的最后一个批注是 SuppressWarnings。该批注的作用…

编程日记2024/04/19 07:00:00

iOS 轻击、触摸和手势的检测

一、检测捏合手势( UIPinchGestureRecognizer): //设定一个实例变量存储手指之间的其起始距离 property (assign, nonatomic) CGFloat initialFontSize;//调用&#xff1a;UIPinchGestureRecognizer *pinch [[UIPinchGestureRecognizeralloc]initWithTarget:selfaction:select…

编程日记2024/04/19 06:30:00

二分法：search insert position 插入位置

问题描述&#xff1a; 给定一个排序数组nums(无重复元素)与目标值target&#xff0c;如果target在nums里 出现&#xff0c;则返回target所在下标&#xff0c;如果target在nums里未出现&#xff0c;则返回target应该 插入位置的数组下标&#xff0c;使得将target插入数组nums后&…

编程日记2024/04/19 06:00:00

c语言课程设计学生籍贯信息记录簿,C语言课程设计 学生籍贯信息记录簿设计.doc...

C语言与程序设计课程设计学生籍贯信息记录簿设计学 院 信息工程班 级 物联1301班学 号 131408119姓 名 滕玲一&#xff0e;设计目的该软件主要是编辑一个学生籍贯信息记录簿记录每个学生信息&#xff0c;包括&#xff1a;学号、姓名、籍贯。具体功能&#xff1a;1.创建信息链表…

编程日记2024/04/19 05:30:00