Back to Leetcode

Readme

Greedy/3551.Minimum-Swaps-to-Sort-by-Digit-Sum/Readme.md

latest481 B
Original Source

3551.Minimum-Swaps-to-Sort-by-Digit-Sum

本质就是两个数组A和B,其中B是A的permutaion。问经过几次swap可以将A变成B。

贪心必然是最优解。对于A的第i个元素而言,我们找到它在B中预期的位置j。那么我们就将A[i]与A[j]交换,这样就至少将A[i]放到了它应该在的位置。不断重复,直至i位置上被换成了预期的数字(即B[i]).

这样的贪心操作是最优的,因为每一步都没有浪费。