博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
[LintCode] Reverse Pairs 翻转对
阅读量:5877 次
发布时间:2019-06-19

本文共 914 字,大约阅读时间需要 3 分钟。

For an array A, if i < j, and A [i] > A [j], called (A [i], A [j]) is a reverse pair.

return total of reverse pairs in A. 
Example
Given A = [2, 4, 1, 3, 5] , (2, 1), (4, 1), (4, 3) are reverse pairs. return 3

这道题跟LeetCode上的那道是一样的,唯一的一点点的小区别是那道题是返回一个向量,表示出原数组中每一个数字的右边比其小的数的个数,而这道题让我们求翻转对的总数,其实就是把每个数字右边比其小的数的个数都加起来即可,具体讲解请参加之前那篇博客,参见代码如下;

class Solution {public:    long long reversePairs(vector
& A) { long long res = 0; vector
v; for (int i = A.size() - 1; i >= 0; --i) { int left = 0, right = v.size(); while (left < right) { int mid = left + (right - left) / 2; if (A[i] > v[mid]) left = mid + 1; else right = mid; } v.insert(v.begin() + right, A[i]); res += right; } return res; }};

本文转自博客园Grandyang的博客,原文链接:,如需转载请自行联系原博主。

你可能感兴趣的文章
JS Cookie
查看>>
ubuntu Unable to locate package sysv-rc-conf
查看>>
笔记:认识.NET平台
查看>>
cocos2d中CCAnimation的使用(cocos2d 1.0以上版本)
查看>>
【吉光片羽】短信验证
查看>>
MacBook如何用Parallels Desktop安装windows7/8
查看>>
gitlab 完整部署实例
查看>>
GNS关于IPS&ASA&PIX&Junos的配置
查看>>
七天学会ASP.NET MVC (四)——用户授权认证问题
查看>>
upgrade to iOS7,how to remove stroyboard?
查看>>
影响企业信息化成败的几点因素
查看>>
SCCM 2016 配置管理系列(Part8)
查看>>
zabbix监控部署
查看>>
struts中的xwork源码下载地址
查看>>
Android硬件抽象层(HAL)深入剖析(二)
查看>>
CDays–4 习题一至四及相关内容解析。
查看>>
L3.十一.匿名函数和map方法
查看>>
java面向对象高级分层实例_实体类
查看>>
android aapt 用法 -- ApkReader
查看>>
[翻译]用 Puppet 搭建易管理的服务器基础架构(3)
查看>>