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

相关文章

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

spoj705( 求不相同的子串个数)

题意:求串s的不同子串的个数 解题思路:任何子串都是某个后缀的前缀,对n个后缀排序,求某个后缀的前缀的个数,减去height[i](第i个后缀与第i-1 个后缀有相同的height[i]个前缀)。 代码如下: #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstrin

poj 1113 凸包+简单几何计算

题意: 给N个平面上的点,现在要在离点外L米处建城墙,使得城墙把所有点都包含进去且城墙的长度最短。 解析: 韬哥出的某次训练赛上A出的第一道计算几何,算是大水题吧。 用convexhull算法把凸包求出来,然后加加减减就A了。 计算见下图: 好久没玩画图了啊好开心。 代码: #include <iostream>#include <cstdio>#inclu

uva 1342 欧拉定理(计算几何模板)

题意: 给几个点,把这几个点用直线连起来,求这些直线把平面分成了几个。 解析: 欧拉定理: 顶点数 + 面数 - 边数= 2。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#inc

uva 11178 计算集合模板题

题意: 求三角形行三个角三等分点射线交出的内三角形坐标。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <stack>#include <vector>#include <

XTU 1237 计算几何

题面: Magic Triangle Problem Description: Huangriq is a respectful acmer in ACM team of XTU because he brought the best place in regional contest in history of XTU. Huangriq works in a big compa

XTU 1233 n个硬币连续m个正面个数(dp)

题面: Coins Problem Description: Duoxida buys a bottle of MaiDong from a vending machine and the machine give her n coins back. She places them in a line randomly showing head face or tail face o

leetcode-24Swap Nodes in Pairs

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode swapPairs(L

leetcode-23Merge k Sorted Lists

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode mergeKLists

C++ | Leetcode C++题解之第393题UTF-8编码验证

题目: 题解: class Solution {public:static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num &