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

Divide the array into two parts and sort them.

For each integer in the first part, count the number of integers that satisfy the condition from the second part. Use the pointer to help you in the counting process.

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>

翻转对

执行通过

错误解答

超出内存限制

超出输出限制

超出时间限制

执行出错

内部出错

编译出错

超时

Restrictions Failed

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

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

示例 1:


输入: [1,3,2,3,1]
输出: 2


示例 2:


输入: [2,4,3,5,1]
输出: 3


注意:

 1. 给定数组的长度不会超过50000。
 2. 输入数组中的所有数字都在32位整数的表示范围内。