leetcode--Maximum Gap--distributed sortingと関係があります.重点的に復習してください.
1584 ワード
https://leetcode.com/problems/maximum-gap/
sortアルゴリズムには比較アルゴリズムの他にdistributed sortがあり、時間効率はO(nlogn)より優れ、O(n)に達することもできる.couting sort,bucket sort,radix sortを含む.
この3つの原理を復習する.リファレンスhttps://www.byvoid.com/blog/sort-radix
ここでbucket sortについて
ここではcounting sortに対する私の疑問を説明し、countが終わったら実際にcをもう一度scanすればソートの結果が得られ、bucket sortになります.
ここではbucket sortにも注意し、要素を各bucketに割り当てる方法では、各bucketの範囲はすでに秩序化されているので、最後に各bucketをscanするだけでソートの結果が得られます.最も極端な場合、最大値がkである場合、k個のbucketが割り当てられる.これでO(n)ですが、
通常
したがってbucket sortは最良のtime complexity O(n)に達できると考えられる.
このテーマはbucket sortかradix sortの後、gapを探せばいいです.
ソートアルゴリズムリファレンスhttp://www.jianshu.com/p/ae97c3ceea8d#、 https://www.byvoid.com/blog/sort-radix https://segmentfault.com/a/1190000003054515 http://blog.csdn.net/cauchyweierstrass/article/details/49781571 https://segmentfault.com/a/1190000002595152
この問題について:http://yucoding.blogspot.hk/2014/12/leetcode-question-maximum-gap.html http://bookshadow.com/weblog/2014/12/14/leetcode-maximum-gap/
sortアルゴリズムには比較アルゴリズムの他にdistributed sortがあり、時間効率はO(nlogn)より優れ、O(n)に達することもできる.couting sort,bucket sort,radix sortを含む.
この3つの原理を復習する.リファレンスhttps://www.byvoid.com/blog/sort-radix
ここでbucket sortについて
， ， C，C[i] A i ， C， 。 ， ， (Bucket Sort)， ， 。
， ， ， Order。ここではcounting sortに対する私の疑問を説明し、countが終わったら実際にcをもう一度scanすればソートの結果が得られ、bucket sortになります.
ここではbucket sortにも注意し、要素を各bucketに割り当てる方法では、各bucketの範囲はすでに秩序化されているので、最後に各bucketをscanするだけでソートの結果が得られます.最も極端な場合、最大値がkである場合、k個のbucketが割り当てられる.これでO(n)ですが、
通常
M N ， O(N) 。 ， ， ， ， 。したがってbucket sortは最良のtime complexity O(n)に達できると考えられる.
このテーマはbucket sortかradix sortの後、gapを探せばいいです.
ソートアルゴリズムリファレンスhttp://www.jianshu.com/p/ae97c3ceea8d#、 https://www.byvoid.com/blog/sort-radix https://segmentfault.com/a/1190000003054515 http://blog.csdn.net/cauchyweierstrass/article/details/49781571 https://segmentfault.com/a/1190000002595152
この問題について:http://yucoding.blogspot.hk/2014/12/leetcode-question-maximum-gap.html http://bookshadow.com/weblog/2014/12/14/leetcode-maximum-gap/