你们会为5岁孩子喂饭吗# Parenting - 为人父母
k*r
1 楼
以前版里贴过的一题
void minMSwap(int[] num, int m), return the min array after m swaps, each
swap happens only between two adjacent elements([4,2,1,3], 2 return [1,4,2,3
] )
4,2,1,3
4,1,2,3
1,4,2,3
当时贴的解法是找最小的元素,判断swap它需要的最少交换次数n,如果n<=m,swap过
来,m -= n,递归, 如果n>m?那就找次小的,重复上面的步骤
这个应该是O(n^2)时间复杂度,因为n次循环,每次循环里面找到符合交换次数的没有
用过的最小位又是O(n)的时间。
我觉得每次循环里面用heap优化,有希望把总时间降到O(nlogn), 但检查或update
heap中元素是否符合交换次数这一步还是要耗掉O(n), 这样总时间还是O(n^2)
哪位大牛贴个nlogn的完整解法?
void minMSwap(int[] num, int m), return the min array after m swaps, each
swap happens only between two adjacent elements([4,2,1,3], 2 return [1,4,2,3
] )
4,2,1,3
4,1,2,3
1,4,2,3
当时贴的解法是找最小的元素,判断swap它需要的最少交换次数n,如果n<=m,swap过
来,m -= n,递归, 如果n>m?那就找次小的,重复上面的步骤
这个应该是O(n^2)时间复杂度,因为n次循环,每次循环里面找到符合交换次数的没有
用过的最小位又是O(n)的时间。
我觉得每次循环里面用heap优化,有希望把总时间降到O(nlogn), 但检查或update
heap中元素是否符合交换次数这一步还是要耗掉O(n), 这样总时间还是O(n^2)
哪位大牛贴个nlogn的完整解法?