LEETCODE 315. 计算右侧小于当前元素的个数(归并)

2024-02-15 19:52

本文主要是介绍LEETCODE 315. 计算右侧小于当前元素的个数(归并),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

请添加图片描述

class Solution {
public:  // 将count声明为publicvector<int> count; vector<int> indexs,tmp;public:vector<int> countSmaller(vector<int>& nums) {//归并int left=0;int right=nums.size()-1;//计数// vector<int> count(nums.size()); count=vector<int>(nums.size());for(int i=0;i<nums.size();i++){count[i]=0;}//index    // vector<int> indexs(nums.size());indexs=vector<int>(nums.size());for(int i=0;i<nums.size();i++){indexs[i]=i;}tmp=vector<int>(nums.size());mergeSort(left,right,nums);// vector<int> counts;// for(int i=0;i<nums.size();i++)//     counts.push_back(n[nums_copy[i]]);return count;}void mergeSort(int left,int right,vector<int>& nums){if(left>=right)return ;int mid=left+(right-left)/2;mergeSort(left,mid,nums);mergeSort(mid+1,right,nums);merge(left,right,nums);}void merge(int left,int right,vector<int>& nums){int mid=left+(right-left)/2;int i=left;int j=mid+1;// vector<int> tmp;int k=0;while(i<=mid && j<=right){if(nums[indexs[i]]>nums[indexs[j]]){count[indexs[i]]+=(right-j)+1;tmp[k++]=indexs[i++];}else{tmp[k++]=indexs[j++];}}while(i<=mid){tmp[k++]=indexs[i++];}while(j<=right){tmp[k++]=indexs[j++];}for(int i=0;i<k;i++){indexs[left+i]=tmp[i];}// tmp.clear();}};

请添加图片描述

Focus:
1 (int left,int right,vector& nums) &没有用取址符会超出内存
2 点在于indexs 按index顺序归并,比较按里面元素
3 tmp index count

这篇关于LEETCODE 315. 计算右侧小于当前元素的个数(归并)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/712380

相关文章

mysql如何查看当前连接数

《mysql如何查看当前连接数》:本文主要介绍mysql如何查看当前连接数问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录mysql查看当前连接数查看mysql数据库允许最大连接数总结mysql查看当前连接数查看当前连接数SHOW STATUS LIKE

C++从序列容器中删除元素的四种方法

《C++从序列容器中删除元素的四种方法》删除元素的方法在序列容器和关联容器之间是非常不同的,在序列容器中,vector和string是最常用的,但这里也会介绍deque和list以供全面了解,尽管在一... 目录一、简介二、移除给定位置的元素三、移除与某个值相等的元素3.1、序列容器vector、deque

C++常见容器获取头元素的方法大全

《C++常见容器获取头元素的方法大全》在C++编程中,容器是存储和管理数据集合的重要工具,不同的容器提供了不同的接口来访问和操作其中的元素,获取容器的头元素(即第一个元素)是常见的操作之一,本文将详细... 目录一、std::vector二、std::list三、std::deque四、std::forwa

Android如何获取当前CPU频率和占用率

《Android如何获取当前CPU频率和占用率》最近在优化App的性能,需要获取当前CPU视频频率和占用率,所以本文小编就来和大家总结一下如何在Android中获取当前CPU频率和占用率吧... 最近在优化 App 的性能,需要获取当前 CPU视频频率和占用率,通过查询资料,大致思路如下:目前没有标准的

Flutter监听当前页面可见与隐藏状态的代码详解

《Flutter监听当前页面可见与隐藏状态的代码详解》文章介绍了如何在Flutter中使用路由观察者来监听应用进入前台或后台状态以及页面的显示和隐藏,并通过代码示例讲解的非常详细,需要的朋友可以参考下... flutter 可以监听 app 进入前台还是后台状态,也可以监听当http://www.cppcn

使用C++实现链表元素的反转

《使用C++实现链表元素的反转》反转链表是链表操作中一个经典的问题,也是面试中常见的考题,本文将从思路到实现一步步地讲解如何实现链表的反转,帮助初学者理解这一操作,我们将使用C++代码演示具体实现,同... 目录问题定义思路分析代码实现带头节点的链表代码讲解其他实现方式时间和空间复杂度分析总结问题定义给定

Python如何计算两个不同类型列表的相似度

《Python如何计算两个不同类型列表的相似度》在编程中,经常需要比较两个列表的相似度,尤其是当这两个列表包含不同类型的元素时,下面小编就来讲讲如何使用Python计算两个不同类型列表的相似度吧... 目录摘要引言数字类型相似度欧几里得距离曼哈顿距离字符串类型相似度Levenshtein距离Jaccard相

CSS3中使用flex和grid实现等高元素布局的示例代码

《CSS3中使用flex和grid实现等高元素布局的示例代码》:本文主要介绍了使用CSS3中的Flexbox和Grid布局实现等高元素布局的方法,通过简单的两列实现、每行放置3列以及全部代码的展示,展示了这两种布局方式的实现细节和效果,详细内容请阅读本文,希望能对你有所帮助... 过往的实现方法是使用浮动加

Java实现Elasticsearch查询当前索引全部数据的完整代码

《Java实现Elasticsearch查询当前索引全部数据的完整代码》:本文主要介绍如何在Java中实现查询Elasticsearch索引中指定条件下的全部数据,通过设置滚动查询参数(scrol... 目录需求背景通常情况Java 实现查询 Elasticsearch 全部数据写在最后需求背景通常情况下

在MyBatis的XML映射文件中<trim>元素所有场景下的完整使用示例代码

《在MyBatis的XML映射文件中<trim>元素所有场景下的完整使用示例代码》在MyBatis的XML映射文件中,trim元素用于动态添加SQL语句的一部分,处理前缀、后缀及多余的逗号或连接符,示... 在MyBATis的XML映射文件中,<trim>元素用于动态地添加SQL语句的一部分,例如SET或W