k*******r 发帖数: 355 | 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的完整解法? | q****m 发帖数: 177 | 2 感觉可以用Dijkstra, 但是不知道对不对
,3
【在 k*******r 的大作中提到】 : 以前版里贴过的一题 : 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次循环,每次循环里面找到符合交换次数的没有
| l*********8 发帖数: 4642 | 3 感觉可以O(m)来求解。 我再看看
,3
【在 k*******r 的大作中提到】 : 以前版里贴过的一题 : 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次循环,每次循环里面找到符合交换次数的没有
| v*****y 发帖数: 68 | 4
,3
不太懂题目,能解释一下什么是“min array”吗?
【在 k*******r 的大作中提到】 : 以前版里贴过的一题 : 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次循环,每次循环里面找到符合交换次数的没有
| k*******r 发帖数: 355 | 5 min array就是把数组看成一个数的话,其数值尽可能小
比如1,4,2,3,这个array比2,1,3,4就小,因为1423这个数小于2134.
所以如果没任何swap限制,min array就会是1234. 题目求的是加了swap限制的
minarray | g*********e 发帖数: 14401 | 6 你找数组里前m个数的最小的,比如第k个,
如果k > 1, 把它移到最前面。m=m-k。重复
如果第一个数最小(k=1),就从第二个数开始找, m不变。重复
最终复杂度是O(m) | n********e 发帖数: 41 | 7 m 能不变 复杂的怎么可能是 O(m)
给你个数组 [1,2,3,....,999999,.....,n], m = 10
复杂的可能是O(m) 么。。。
【在 g*********e 的大作中提到】 : 你找数组里前m个数的最小的,比如第k个, : 如果k > 1, 把它移到最前面。m=m-k。重复 : 如果第一个数最小(k=1),就从第二个数开始找, m不变。重复 : 最终复杂度是O(m)
| g*********e 发帖数: 14401 | 8
哦 那就是O(nm)
【在 n********e 的大作中提到】 : m 能不变 复杂的怎么可能是 O(m) : 给你个数组 [1,2,3,....,999999,.....,n], m = 10 : 复杂的可能是O(m) 么。。。
| k*******r 发帖数: 355 | 9 当m大于n (或者comparable with n)时,这个算法复杂度不还是O(n^2)么
而且我觉得每次都从头找最小的肯定不行,还是要用类似于heap的结构,使得下一次找
最小元素不必从头找起
【在 g*********e 的大作中提到】 : 你找数组里前m个数的最小的,比如第k个, : 如果k > 1, 把它移到最前面。m=m-k。重复 : 如果第一个数最小(k=1),就从第二个数开始找, m不变。重复 : 最终复杂度是O(m)
| M*******a 发帖数: 1633 | | | | w*******e 发帖数: 395 | 11 1. Establish a min heap and the heap contains the index of each element;
2. every time get the min of the remaining array, if m>(index-current
position), put the min into the array, continue step 2 until m<(index-
current position)
3. if m is not enough to move the remaining min to the current position, get
rid of the min in the heap and get the next min until m is enough
the tricky point is how to adjust the index of each element because after
each move the index has been changed.
The complexity is m*log(n) | n********e 发帖数: 41 | 12 感觉 heap 不 stable
如果有重复元素的话 不能保证每次heap的最小值 是离 current 最近的最小值
get
【在 w*******e 的大作中提到】 : 1. Establish a min heap and the heap contains the index of each element; : 2. every time get the min of the remaining array, if m>(index-current : position), put the min into the array, continue step 2 until m<(index- : current position) : 3. if m is not enough to move the remaining min to the current position, get : rid of the min in the heap and get the next min until m is enough : the tricky point is how to adjust the index of each element because after : each move the index has been changed. : The complexity is m*log(n)
| g*********e 发帖数: 14401 | 13
get
how to "adjust the index of each element because after
each move the index has been changed"
【在 w*******e 的大作中提到】 : 1. Establish a min heap and the heap contains the index of each element; : 2. every time get the min of the remaining array, if m>(index-current : position), put the min into the array, continue step 2 until m<(index- : current position) : 3. if m is not enough to move the remaining min to the current position, get : rid of the min in the heap and get the next min until m is enough : the tricky point is how to adjust the index of each element because after : each move the index has been changed. : The complexity is m*log(n)
| k*******r 发帖数: 355 | 14 我来想个"how to adjust the index of each element because after
each move the index has been change"
这个adjust必须在log(n)时间内完成不然就没意义了
我的想法是不需要真的adjusted index of each element, 我们只需要给定一个原始
index, 知道这个index后面有多少元素已经被用了。比如某元素原始index为5, 同时
我们知道5后面已经有3个元素被用了,那么现在此元素新的index就是5+3=8
怎么在log(n)时间内知道给定index后面多少元素被用了呢,用2叉平衡树分查找或者
bitmap都可以快速做到 | s******6 发帖数: 12 | 15
怎么在log(n)内知道?
另外除了这个trick,还有个就是如果某次的move为0,那么那些前面被抛弃过的node就
有再次被选中的机会(如仅超过限制1)
【在 k*******r 的大作中提到】 : 我来想个"how to adjust the index of each element because after : each move the index has been change" : 这个adjust必须在log(n)时间内完成不然就没意义了 : 我的想法是不需要真的adjusted index of each element, 我们只需要给定一个原始 : index, 知道这个index后面有多少元素已经被用了。比如某元素原始index为5, 同时 : 我们知道5后面已经有3个元素被用了,那么现在此元素新的index就是5+3=8 : 怎么在log(n)时间内知道给定index后面多少元素被用了呢,用2叉平衡树分查找或者 : bitmap都可以快速做到
|
|