@ninijia 在 Leetcode每日一题练习 ------ 2948. 交换得到字典序最小的数组 中发帖
从Leetcode 每日一题练习继续讨论:
2948. 交换得到字典序最小的数组
2948. Make Lexicographically Smallest Array by Swapping Elements
题解
本题考虑对任意数字m,能与其交换位置的数字的范围在m-limit~m+limit之间。如果存在m+limit这一数字,则实际m可交换的数字范围就扩大为m-limit~m+limit+limit之间。因为m总可以通过先让m+limit和更大的数字交换位置再让m和m+limit交换位置来与更大的数字交换位置,此时可互相交换位置的数字范围变为m-limit~m+limit+limit。只要记录下该范围内的全部数字及其位置,再对范围内的全部数字排序,按序放在范围内对应的全部位置上。
对于在范围外的数字,则需要同样记录其可交换位置的范围,这样我们需要记录不同的范围,范围内已经存...