Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

面试题3 数组中重复的数字 #25

Closed
ghost opened this issue Sep 25, 2018 · 2 comments
Closed

面试题3 数组中重复的数字 #25

ghost opened this issue Sep 25, 2018 · 2 comments

Comments

@ghost
Copy link

ghost commented Sep 25, 2018

第二版书中41页提到,"虽然有两个循环,但每个数字最多只要交换两次就能找到属于它自己的位置,所以总时间复杂度是O(n)"

这里不太明白,书中给的例子第一个下标就交换了三次,这个O(n)是怎样得出的呢?

@zhedahht
Copy link
Owner

从0到n-1里面的任意一个数字i,如果开始它不在下标为i的位置,通过交换把它放到下标为i的位置。如果下次再遇到值为i的数字,当我们再想把它交换到下标为i的位置时,就会发现下标为i的位置已经有一个值为i的数字,就找到一个重复的数字了。

我们通过这这种交换,把从0到n-1的每个数字都放到和值相等的下标的位置。一个数字最多只需要交换两次。所以交换的次数是O(n)。

@ghost
Copy link
Author

ghost commented Sep 26, 2018

明白了,谢谢。

@ghost ghost closed this as completed Sep 26, 2018
This issue was closed.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant