你有没有想过，既然你认为排序能够预测到每一个数的最终落点并直接交换，那它为什么不是O(n)的？
by mashduihca @ 2023-03-02 16:14:17
然后怎么办?本来想写一个最朴素的bfs,但看到数据范围了后就打消了这个念头,题解不大看得懂
by caojiaming @ 2023-03-02 16:18:27
@[caojiaming](/user/775551) 显然每个数最优的方案是一步交换到序列有序后自己所属的位置。需要证明吗？
by mashduihca @ 2023-03-02 16:29:09
这样说的话把每个位置扫一遍,每扫一次就是O(n),一共不是又成O(n²)了吗？？？
by caojiaming @ 2023-03-02 16:34:15
@[mashduihca](/user/494183)
by caojiaming @ 2023-03-02 16:35:01
@[caojiaming](/user/775551) 扫一遍是O(n)，判断有序后每个元素所属的位置只需要sort一遍就好了啊，你可以分开处理。
by mashduihca @ 2023-03-02 16:42:09
结论：答案是 n - 置换环个数
by jijidawang @ 2023-03-02 16:47:42
@[jijidawang](/user/227514) 这题不是直接对着目标序列交换就行了吗，为什么还要跑置换环
by Caiest_Oier @ 2023-03-02 17:41:56