global-and-local-inversions

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given an integer array <code>nums</code> of length <code>n</code> which represents a permutation of all the integers in the range <code>[0, n - 1]</code>.

The number of global inversions is the number of the different pairs <code>(i, j)</code> where:

<ul>
	<li><code>0 &lt;= i &lt; j &lt; n</code></li>
	<li><code>nums[i] &gt; nums[j]</code></li>
</ul>

The number of local inversions is the number of indices <code>i</code> where:

<ul>
	<li><code>0 &lt;= i &lt; n - 1</code></li>
	<li><code>nums[i] &gt; nums[i + 1]</code></li>
</ul>

Return <code>true</code> if the number of global inversions is equal to the number of local inversions.

&nbsp;
Example 1:

<pre>
Input: nums = [1,0,2]
Output: true
Explanation: There is 1 global inversion and 1 local inversion.
</pre>

Example 2:

<pre>
Input: nums = [1,2,0]
Output: false
Explanation: There are 2 global inversions and 1 local inversion.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>n == nums.length</code></li>
	<li><code>1 &lt;= n &lt;= 105</code></li>
	<li><code>0 &lt;= nums[i] &lt; n</code></li>
	<li>All the integers of <code>nums</code> are unique.</li>
	<li><code>nums</code> is a permutation of all the numbers in the range <code>[0, n - 1]</code>.</li>
</ul>

isIdealPermutation

Global and Local Inversions

Array

Math

给你一个长度为 <code>n</code> 的整数数组 <code>nums</code> ，表示由范围 <code>[0, n - 1]</code> 内所有整数组成的一个排列。

全局倒置 的数目等于满足下述条件不同下标对 <code>(i, j)</code> 的数目：

<ul>
	<li><code>0 &lt;= i &lt; j &lt; n</code></li>
	<li><code>nums[i] &gt; nums[j]</code></li>
</ul>

局部倒置 的数目等于满足下述条件的下标 <code>i</code> 的数目：

<ul>
	<li><code>0 &lt;= i &lt; n - 1</code></li>
	<li><code>nums[i] &gt; nums[i + 1]</code></li>
</ul>

当数组 <code>nums</code> 中 全局倒置 的数量等于 局部倒置 的数量时，返回 <code>true</code> ；否则，返回 <code>false</code> 。

&nbsp;

示例 1：

<pre>
输入：nums = [1,0,2]
输出：true
解释：有 1 个全局倒置，和 1 个局部倒置。
</pre>

示例 2：

<pre>
输入：nums = [1,2,0]
输出：false
解释：有 2 个全局倒置，和 1 个局部倒置。
</pre>
&nbsp;

提示：

<ul>
	<li><code>n == nums.length</code></li>
	<li><code>1 &lt;= n &lt;= 105</code></li>
	<li><code>0 &lt;= nums[i] &lt; n</code></li>
	<li><code>nums</code> 中的所有整数 互不相同</li>
	<li><code>nums</code> 是范围 <code>[0, n - 1]</code> 内所有数字组成的一个排列</li>
</ul>