我有这个数组A = <3,2,9,0,7,5,4,8,6,1>
我想写下所有最差的分区,这些是正确的吗?谢谢
a1 = <0,2,9,3,7,5,4,8,6,1>
a2 = <1,9,3,7,5,4,8,6,2>
a3 = <2,3,7,5,4,8,6,9>
a4 = <3,7,5,4,8,6,9>
a5 = <4,5,7,8,6,9>
a6 = <5,7,8,6,9>
a7 = <6,8,7,9>
a8 = <7,8,9>
a9 = <8,9>
a10 = <9>
最佳答案
我的理解是,您想要显示给定数组的最差分区序列(类似于 quicksort 执行的分区)。
在这种情况下,您可以对数组进行排序,然后显示数组的所有“尾部”,从索引 0 开始,到索引 n-1 结束。
在您的示例中,排序后的数组是:
[0,1,2,3,4,5,6,7,8,9]
然后尾部是:
[0,1,2,3,4,5,6,7,8,9]
[1,2,3,4,5,6,7,8,9]
[2,3,4,5,6,7,8,9]
...
[8,9]
[9]
如果显示所有分区,那么这是一个 O(n^2) 算法(显然无法改进)。如果您只需要显示枢轴,则可以在 O(n*log n) 内完成。
关于java - 关于随机选择算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/3067746/