minimum-swaps-to-sort-by-digit-sum

java

python3

python

javascript

typescript

csharp

golang

kotlin

swift

rust

ruby

dart

scala

elixir

erlang

racket

cangjie

bash

mysql

mssql

postgresql

oraclesql

pythondata

Algorithms

You are given an array <code>nums</code> of distinct positive integers. You need to sort the array in increasing order based on the sum of the digits of each number. If two numbers have the same digit sum, the smaller number appears first in the sorted order.

Return the minimum number of swaps required to rearrange <code>nums</code> into this sorted order.

A swap is defined as exchanging the values at two distinct positions in the array.

&nbsp;
Example 1:

<div class="example-block">
Input: nums = [37,100]

Output: 1

Explanation:

<ul>
	<li>Compute the digit sum for each integer: <code>[3 + 7 = 10, 1 + 0 + 0 = 1] &rarr; [10, 1]</code></li>
	<li>Sort the integers based on digit sum: <code>[100, 37]</code>. Swap <code>37</code> with <code>100</code> to obtain the sorted order.</li>
	<li>Thus, the minimum number of swaps required to rearrange <code>nums</code> is 1.</li>
</ul>
</div>

Example 2:

<div class="example-block">
Input: nums = [22,14,33,7]

Output: 0

Explanation:

<ul>
	<li>Compute the digit sum for each integer: <code>[2 + 2 = 4, 1 + 4 = 5, 3 + 3 = 6, 7 = 7] &rarr; [4, 5, 6, 7]</code></li>
	<li>Sort the integers based on digit sum: <code>[22, 14, 33, 7]</code>. The array is already sorted.</li>
	<li>Thus, the minimum number of swaps required to rearrange <code>nums</code> is 0.</li>
</ul>
</div>

Example 3:

<div class="example-block">
Input: nums = [18,43,34,16]

Output: 2

Explanation:

<ul>
	<li>Compute the digit sum for each integer: <code>[1 + 8 = 9, 4 + 3 = 7, 3 + 4 = 7, 1 + 6 = 7] &rarr; [9, 7, 7, 7]</code></li>
	<li>Sort the integers based on digit sum: <code>[16, 34, 43, 18]</code>. Swap <code>18</code> with <code>16</code>, and swap <code>43</code> with <code>34</code> to obtain the sorted order.</li>
	<li>Thus, the minimum number of swaps required to rearrange <code>nums</code> is 2.</li>
</ul>
</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>nums</code> consists of distinct positive integers.</li>
</ul>

第 450 场周赛

weekly-contest-450

minSwaps

高级工程师

Minimum Swaps to Sort by Digit Sum

Array

Hash Table

Sorting

给你一个由 互不相同&nbsp;的正整数组成的数组 <code>nums</code>，需要根据每个数字的数位和（即每一位数字相加求和）按&nbsp;升序&nbsp;对数组进行排序。如果两个数字的数位和相等，则较小的数字排在前面。

返回将 <code>nums</code> 排列为上述排序顺序所需的&nbsp;最小&nbsp;交换次数。

一次&nbsp;交换&nbsp;定义为交换数组中两个不同位置的值。

&nbsp;

示例 1：

<div class="example-block">
输入: nums = [37,100]

输出: 1

解释:

<ul>
	<li>计算每个整数的数位和：<code>[3 + 7 = 10, 1 + 0 + 0 = 1] → [10, 1]</code></li>
	<li>根据数位和排序：<code>[100, 37]</code>。将 <code>37</code> 与 <code>100</code> 交换，得到排序后的数组。</li>
	<li>因此，将 <code>nums</code> 排列为排序顺序所需的最小交换次数为 1。</li>
</ul>
</div>

示例 2：

<div class="example-block">
输入: nums = [22,14,33,7]

输出: 0

解释:

<ul>
	<li>计算每个整数的数位和：<code>[2 + 2 = 4, 1 + 4 = 5, 3 + 3 = 6, 7 = 7] → [4, 5, 6, 7]</code></li>
	<li>根据数位和排序：<code>[22, 14, 33, 7]</code>。数组已经是排序好的。</li>
	<li>因此，将 <code>nums</code> 排列为排序顺序所需的最小交换次数为 0。</li>
</ul>
</div>

示例 3：

<div class="example-block">
输入: nums = [18,43,34,16]

输出: 2

解释:

<ul>
	<li>计算每个整数的数位和：<code>[1 + 8 = 9, 4 + 3 = 7, 3 + 4 = 7, 1 + 6 = 7] → [9, 7, 7, 7]</code></li>
	<li>根据数位和排序：<code>[16, 34, 43, 18]</code>。将 <code>18</code> 与 <code>16</code> 交换，再将 <code>43</code> 与 <code>34</code> 交换，得到排序后的数组。</li>
	<li>因此，将 <code>nums</code> 排列为排序顺序所需的最小交换次数为 2。</li>
</ul>
</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>nums</code> 由 互不相同 的正整数组成。</li>
</ul>