[数据结构与算法]每个数字最多只要交换两次就能找到属于它自己的位置？

剑指offer中面试题3 数组中重复的数字 题目一：

虽然有两重循环,但是每个数字最多只要交换两次就能找到属于它自己的位置,因此总的时间复杂度是O(n)。

看到这里有点迷惑，不是只需要交换一次吗？

原因是有一次可能是被动交换，例子：{1,3,2,0,2,5,3} ，此时第0个数字是1，与下标不相等，所以将它与下标为1的数字3交换。（注意这里3就是被动交换）

得到数组{3,1,2,0,2,5,3}，此时会继续交换第0个数字3和第3个数字0，得到数组{0,1,3,2,5,3}。（这里3就是主动交换）。

所以每个数字最多只要交换两次就能找到属于它自己的位置。