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都可以快速做到
|
|
