reverse-pairs

java

python3

python

javascript

typescript

csharp

golang

kotlin

swift

rust

ruby

dart

scala

elixir

erlang

racket

cangjie

bash

mysql

mssql

postgresql

oraclesql

pythondata

Algorithms

Given an integer array <code>nums</code>, return the number of reverse pairs in the array.

A reverse pair is a pair <code>(i, j)</code> where:

<ul>
	<li><code>0 &lt;= i &lt; j &lt; nums.length</code> and</li>
	<li><code>nums[i] &gt; 2 * nums[j]</code>.</li>
</ul>

&nbsp;
Example 1:

<pre>
Input: nums = [1,3,2,3,1]
Output: 2
Explanation: The reverse pairs are:
(1, 4) --&gt; nums[1] = 3, nums[4] = 1, 3 &gt; 2 * 1
(3, 4) --&gt; nums[3] = 3, nums[4] = 1, 3 &gt; 2 * 1
</pre>

Example 2:

<pre>
Input: nums = [2,4,3,5,1]
Output: 3
Explanation: The reverse pairs are:
(1, 4) --&gt; nums[1] = 4, nums[4] = 1, 4 &gt; 2 * 1
(2, 4) --&gt; nums[2] = 3, nums[4] = 1, 3 &gt; 2 * 1
(3, 4) --&gt; nums[3] = 5, nums[4] = 1, 5 &gt; 2 * 1
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= nums.length &lt;= 5 * 104</code></li>
	<li><code>-231 &lt;= nums[i] &lt;= 231 - 1</code></li>
</ul>

reversePairs

Reverse Pairs

Count of Smaller Numbers After Self

count-of-smaller-numbers-after-self

计算右侧小于当前元素的个数

Count of Range Sum

count-of-range-sum

区间和的个数

Binary Indexed Tree

Segment Tree

Array

Binary Search

Divide and Conquer

Ordered Set

树堆

Merge Sort

给定一个数组&nbsp;<code>nums</code>&nbsp;，如果&nbsp;<code>i &lt; j</code>&nbsp;且&nbsp;<code>nums[i] &gt; 2*nums[j]</code>&nbsp;我们就将&nbsp;<code>(i, j)</code>&nbsp;称作一个重要翻转对。

你需要返回给定数组中的重要翻转对的数量。

示例 1:

<pre>
输入: [1,3,2,3,1]
输出: 2
</pre>

示例 2:

<pre>
输入: [2,4,3,5,1]
输出: 3
</pre>

注意:

<ol>
	<li>给定数组的长度不会超过<code>50000</code>。</li>
	<li>输入数组中的所有数字都在32位整数的表示范围内。</li>
</ol>