minimum-adjacent-swaps-to-reach-the-kth-smallest-number

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 a string <code>num</code>, representing a large integer, and an integer <code>k</code>.

We call some integer wonderful if it is a permutation of the digits in <code>num</code> and is greater in value than <code>num</code>. There can be many wonderful integers. However, we only care about the smallest-valued ones.

<ul>
	<li>For example, when <code>num = &quot;5489355142&quot;</code>:

	<ul>
		<li>The 1st smallest wonderful integer is <code>&quot;5489355214&quot;</code>.</li>
		<li>The 2nd smallest wonderful integer is <code>&quot;5489355241&quot;</code>.</li>
		<li>The 3rd smallest wonderful integer is <code>&quot;5489355412&quot;</code>.</li>
		<li>The 4th smallest wonderful integer is <code>&quot;5489355421&quot;</code>.</li>
	</ul>
	</li>
</ul>

Return the minimum number of adjacent digit swaps that needs to be applied to <code>num</code> to reach the <code>kth</code> smallest wonderful integer.

The tests are generated in such a way that <code>kth</code>&nbsp;smallest wonderful integer exists.

&nbsp;
Example 1:

<pre>
Input: num = &quot;5489355142&quot;, k = 4
Output: 2
Explanation: The 4th smallest wonderful number is &quot;5489355421&quot;. To get this number:
- Swap index 7 with index 8: &quot;5489355142&quot; -&gt; &quot;5489355412&quot;
- Swap index 8 with index 9: &quot;5489355412&quot; -&gt; &quot;5489355421&quot;
</pre>

Example 2:

<pre>
Input: num = &quot;11112&quot;, k = 4
Output: 4
Explanation: The 4th smallest wonderful number is &quot;21111&quot;. To get this number:
- Swap index 3 with index 4: &quot;11112&quot; -&gt; &quot;11121&quot;
- Swap index 2 with index 3: &quot;11121&quot; -&gt; &quot;11211&quot;
- Swap index 1 with index 2: &quot;11211&quot; -&gt; &quot;12111&quot;
- Swap index 0 with index 1: &quot;12111&quot; -&gt; &quot;21111&quot;
</pre>

Example 3:

<pre>
Input: num = &quot;00123&quot;, k = 1
Output: 1
Explanation: The 1st smallest wonderful number is &quot;00132&quot;. To get this number:
- Swap index 3 with index 4: &quot;00123&quot; -&gt; &quot;00132&quot;
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>2 &lt;= num.length &lt;= 1000</code></li>
	<li><code>1 &lt;= k &lt;= 1000</code></li>
	<li><code>num</code> only consists of digits.</li>
</ul>

getMinSwaps

Minimum Adjacent Swaps to Reach the Kth Smallest Number

Next Permutation

next-permutation

下一个排列

Greedy

Two Pointers

String

给你一个表示大整数的字符串 <code>num</code> ，和一个整数 <code>k</code> 。

如果某个整数是 <code>num</code> 中各位数字的一个 排列 且它的 值大于 <code>num</code> ，则称这个整数为 妙数 。可能存在很多妙数，但是只需要关注 值最小 的那些。

<ul>
	<li>例如，<code>num = "5489355142"</code> ：

	<ul>
		<li>第 1 个最小妙数是 <code>"5489355214"</code></li>
		<li>第 2 个最小妙数是 <code>"5489355241"</code></li>
		<li>第 3 个最小妙数是 <code>"5489355412"</code></li>
		<li>第 4 个最小妙数是 <code>"5489355421"</code></li>
	</ul>
	</li>
</ul>

返回要得到第 <code>k</code> 个 最小妙数 需要对 <code>num</code> 执行的 相邻位数字交换的最小次数 。

测试用例是按存在第 <code>k</code> 个最小妙数而生成的。

 

示例 1：

<pre>输入：num = "5489355142", k = 4
输出：2
解释：第 4 个最小妙数是 "5489355421" ，要想得到这个数字：
- 交换下标 7 和下标 8 对应的位："5489355142" -&gt; "5489355412"
- 交换下标 8 和下标 9 对应的位："5489355412" -&gt; "5489355421"
</pre>

示例 2：

<pre>输入：num = "11112", k = 4
输出：4
解释：第 4 个最小妙数是 "21111" ，要想得到这个数字：
- 交换下标 3 和下标 4 对应的位："11112" -&gt; "11121"
- 交换下标 2 和下标 3 对应的位："11121" -&gt; "11211"
- 交换下标 1 和下标 2 对应的位："11211" -&gt; "12111"
- 交换下标 0 和下标 1 对应的位："12111" -&gt; "21111"
</pre>

示例 3：

<pre>输入：num = "00123", k = 1
输出：1
解释：第 1 个最小妙数是 "00132" ，要想得到这个数字：
- 交换下标 3 和下标 4 对应的位："00123" -&gt; "00132"
</pre>

 

提示：

<ul>
	<li><code>2 &lt;= num.length &lt;= 1000</code></li>
	<li><code>1 &lt;= k &lt;= 1000</code></li>
	<li><code>num</code> 仅由数字组成</li>
</ul>