minimum-adjacent-swaps-to-partition-array

java

python3

python

javascript

typescript

csharp

golang

kotlin

swift

rust

ruby

dart

scala

elixir

erlang

racket

cangjie

bash

mysql

mssql

postgresql

oraclesql

pythondata

Replace each element with its group number: <code>0</code> if it is less than <code>a</code>, <code>1</code> if it is in the range <code>[a, b]</code>, and <code>2</code> if it is greater than <code>b</code>.

After this replacement, the goal is to make the array sorted in non-decreasing order.

With adjacent swaps, the minimum number of swaps needed is the number of inversions in this group array.

Since there are only three possible group values, scan from left to right and count how many previous values are greater than the current value.

Algorithms

You are given an integer array <code>nums</code> and two integers <code>a</code> and <code>b</code> such that <code>a &lt; b</code>.

An array is called good if it can be split into three contiguous parts, in this order, such that:

<ul>
	<li>Every element in the first part is less than <code>a</code>.</li>
	<li>Every element in the second part is in the range <code>[a, b]</code> inclusive.</li>
	<li>Every element in the third part is greater than <code>b</code>.</li>
</ul>

Any of the three parts may be empty.

In one adjacent swap, you may swap two neighboring elements of <code>nums</code>.

Return the minimum number of adjacent swaps required to make <code>nums</code> good. Since the answer may be very large, return it modulo <code>109 + 7</code>.

&nbsp;
Example 1:

<div class="example-block">
Input: nums = [1,3,2,4,5,6], a = 3, b = 4

Output: 1

Explanation:

<ul>
	<li>Swap <code>nums[1]</code> and <code>nums[2]</code>. The array becomes <code>[1, 2, 3, 4, 5, 6]</code>.</li>
	<li>This array is good because it can be split into <code>[1, 2]</code>, <code>[3, 4]</code>, and <code>[5, 6]</code>.</li>
</ul>
</div>

Example 2:

<div class="example-block">
Input: nums = [9,7,5,3], a = 4, b = 8

Output: 5

Explanation:

One sequence of optimal swaps is as follows:

<ul>
	<li>Swap <code>nums[2]</code> and <code>nums[3]</code>. The array becomes <code>[9, 7, 3, 5]</code>.</li>
	<li>Swap <code>nums[1]</code> and <code>nums[2]</code>. The array becomes <code>[9, 3, 7, 5]</code>.</li>
	<li>Swap <code>nums[0]</code> and <code>nums[1]</code>. The array becomes <code>[3, 9, 7, 5]</code>.</li>
	<li>Swap <code>nums[1]</code> and <code>nums[2]</code>. The array becomes <code>[3, 7, 9, 5]</code>.</li>
	<li>Swap <code>nums[2]</code> and <code>nums[3]</code>. The array becomes <code>[3, 7, 5, 9]</code>.</li>
	<li>This array is good because it can be split into <code>[3]</code>, <code>[7, 5]</code>, and <code>[9]</code>.</li>
</ul>
</div>

Example 3:

<div class="example-block">
Input: nums = [3,7,5,9], a = 4, b = 8

Output: 0

Explanation:

The array is already good. No swaps are needed.
</div>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= nums.length &lt;= 105</code></li>
	<li><code>​​​​​​​1 &lt;= nums[i] &lt;= 109</code></li>
	<li><code>1 &lt;= a &lt; b &lt;= 109​​​​​​​</code></li>
</ul>

第 187 场双周赛

biweekly-contest-187

minAdjacentSwaps

资深工程师

Minimum Adjacent Swaps to Partition Array

Greedy

Array

给你一个整数数组 <code>nums</code> 和两个整数 <code>a</code> 和 <code>b</code>，满足 <code>a &lt; b</code>。

如果一个数组可以按顺序分成三个 连续 的部分，并且满足以下条件，则称其为 好数组：

<ul>
	<li>第一部分中的每个元素都 小于 <code>a</code>。</li>
	<li>第二部分中的每个元素都 在 闭区间 <code>[a, b]</code> 内。</li>
	<li>第三部分中的每个元素都 大于 <code>b</code>。</li>
</ul>

这三个部分中的任意一个都 可以 为空。


在一次 相邻交换 中，你可以交换 <code>nums</code> 的两个 相邻 元素。

返回使 <code>nums</code> 成为好数组所需的 最少 相邻交换次数。由于答案可能非常大，请将其对 <code>109 + 7</code> 取余 后返回。

&nbsp;

示例 1：

<div class="example-block">
输入： nums = [1,3,2,4,5,6], a = 3, b = 4

输出： 1

解释：

<ul>
	<li>交换 <code>nums[1]</code> 和 <code>nums[2]</code>。数组变为 <code>[1, 2, 3, 4, 5, 6]</code>。</li>
	<li>这个数组是好数组，因为它可以分为 <code>[1, 2]</code>、<code>[3, 4]</code> 和 <code>[5, 6]</code>。</li>
</ul>
</div>

示例 2：

<div class="example-block">
输入： nums = [9,7,5,3], a = 4, b = 8

输出： 5

解释：

一种最佳交换序列如下：

<ul>
	<li>交换 <code>nums[2]</code> 和 <code>nums[3]</code>。数组变为 <code>[9, 7, 3, 5]</code>。</li>
	<li>交换 <code>nums[1]</code> 和 <code>nums[2]</code>。数组变为 <code>[9, 3, 7, 5]</code>。</li>
	<li>交换 <code>nums[0]</code> 和 <code>nums[1]</code>。数组变为 <code>[3, 9, 7, 5]</code>。</li>
	<li>交换 <code>nums[1]</code> 和 <code>nums[2]</code>。数组变为 <code>[3, 7, 9, 5]</code>。</li>
	<li>交换 <code>nums[2]</code> 和 <code>nums[3]</code>。数组变为 <code>[3, 7, 5, 9]</code>。</li>
	<li>这个数组是好数组，因为它可以分为 <code>[3]</code>、<code>[7, 5]</code> 和 <code>[9]</code>。</li>
</ul>
</div>

示例 3：

<div class="example-block">
输入： nums = [3,7,5,9], a = 4, b = 8

输出： 0

解释：

该数组已经是好数组。不需要交换。
</div>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= nums.length &lt;= 105</code></li>
	<li><code>1 &lt;= nums[i] &lt;= 109</code></li>
	<li><code>1 &lt;= a &lt; b &lt;= 109</code></li>
</ul>

划分数组的最少相邻交换次数

执行通过

错误解答

超出内存限制

超出输出限制

超出时间限制

执行出错

内部出错

编译出错

超时

Restrictions Failed

给你一个整数数组 nums 和两个整数 a 和 b，满足 a < b。

如果一个数组可以按顺序分成三个 连续 的部分，并且满足以下条件，则称其为 好数组：

 * 第一部分中的每个元素都 小于 a。
 * 第二部分中的每个元素都 在 闭区间 [a, b] 内。
 * 第三部分中的每个元素都 大于 b。

这三个部分中的任意一个都 可以 为空。

在一次 相邻交换 中，你可以交换 nums 的两个 相邻 元素。

返回使 nums 成为好数组所需的 最少 相邻交换次数。由于答案可能非常大，请将其对 109 + 7 取余 后返回。

 

示例 1：

输入： nums = [1,3,2,4,5,6], a = 3, b = 4

输出： 1

解释：

 * 交换 nums[1] 和 nums[2]。数组变为 [1, 2, 3, 4, 5, 6]。
 * 这个数组是好数组，因为它可以分为 [1, 2]、[3, 4] 和 [5, 6]。

示例 2：

输入： nums = [9,7,5,3], a = 4, b = 8

输出： 5

解释：

一种最佳交换序列如下：

 * 交换 nums[2] 和 nums[3]。数组变为 [9, 7, 3, 5]。
 * 交换 nums[1] 和 nums[2]。数组变为 [9, 3, 7, 5]。
 * 交换 nums[0] 和 nums[1]。数组变为 [3, 9, 7, 5]。
 * 交换 nums[1] 和 nums[2]。数组变为 [3, 7, 9, 5]。
 * 交换 nums[2] 和 nums[3]。数组变为 [3, 7, 5, 9]。
 * 这个数组是好数组，因为它可以分为 [3]、[7, 5] 和 [9]。

示例 3：

输入： nums = [3,7,5,9], a = 4, b = 8

输出： 0

解释：

该数组已经是好数组。不需要交换。

 

提示：

 * 1 <= nums.length <= 105
 * 1 <= nums[i] <= 109
 * 1 <= a < b <= 109