g********r
发帖数: 58 | 1 An operation "swap" means removing an element from the array and appending
it at the back of the same array. Find the minimum number of "swaps" needed
to sort that array.
Eg :- 3124
Output: 2 (3124->1243->1234)
看到版上有人讨论这道题， 总觉得应该有更优解。 而且假设 数字是从 1-n 有些牵强
。昨天想到了一个解法，今天又稍稍更新了一下。个人的理解 大家看看有没有错。谢
谢！
1. 如果数组长度是n，最多就需要swap n－1次，就是每个元素 最多只需要swap一次。
我们并不需要关心哪个先哪个后swap。 那么 我们就一个一个元素的判断那些需要swap。
2. 首先 如果 给定元素的右边 有更小的值，这个元素就需要swap， 比如上例中的3
3. 然后，再看 剩下的没有swap的元素，如果值比 “在第二步中需要swap的所有元素
的最小值” 大， 那这个元素 就需要 swap， 比如上例，124 中的4 比 3大， 4 就
需要swap
这个解法 O（n）time 常数space，
附上 Pseudo Code
Int minStep(Array A)
swapMin = INT_MAX
rightMin = INT_MAX
for (int i = len(A)-1; i<=0; i--)
if A[i] > rightMin && swapMin < A[i]
swapMin = A[i]
else
rightMin = A[i]
stepCnt = 0
for (int i = 0; i < len(A); i++ )
if A[i] > swapMin
stepCnt++
return stepCnt+1 |
b*******e
发帖数: 217 | 2 incorrect.
see example 3214
first round (1) 32 needs swap
get 1432
second round (2) 4 need to swap
get 1324
not sorted.
I guess needs to use some advanced data structure like stack....
keep tracking the local min.... then pop us the elements larger than the
local min and insert them to the end one by one.
(1) push 32 into stack.
(2) when hit 1, see 1 is local min
(3) pop up 2,3 and insert them to the back of the array
(4) now array is 1423.
(5) the array pointer now go to 1 (note we can track this index with the pop
of the stack). push 1 and 4 into stack.
(6) now find 2 (index 2 in the arr) is a local min
(7) pop 4 out stack (1 not pop out since it is smaller than 2).
(8) insert 4 to the end of the arr.
(9) now the arr is 1234. scanning from index 1 to index 3. no local min any
more. the array is sorted. For this example, sorted in two steps.
not sure sbout the complexity. space compexity is o(n) to maintain the stack
.
When the origniall array is ascent or descent, the time complexity are both
o(n).
not sure about general complexity. |
b*******e
发帖数: 217 | 3 works for 3124 too
(1) push 3 into stack
(2) find 1 is a local min
(3) pop out 3 from the stack and insert it to the back of the array
(4) now array becomes 1243 and the pointer to the array go to 0.
(5) now push 124 into stack. find 3 is a local min
(6) pop out 4 (don't pop out 12 since they are smalelr than 3).
(7) insert 4 to the end of the array.
(8) sorted ast 1234.
The number of swap can be decidied during process above. anyone can help to
analyze the time complexity? |
b*******e
发帖数: 217 | 4 don't work either. seems also need to track local high. |
g********r
发帖数: 58 | 5 不需要 真的去swap吧？
问题不是去找minimum step吗？
to
【在 b*******e 的大作中提到】
: works for 3124 too
: (1) push 3 into stack
: (2) find 1 is a local min
: (3) pop out 3 from the stack and insert it to the back of the array
: (4) now array becomes 1243 and the pointer to the array go to 0.
: (5) now push 124 into stack. find 3 is a local min
: (6) pop out 4 (don't pop out 12 since they are smalelr than 3).
: (7) insert 4 to the end of the array.
: (8) sorted ast 1234.
: The number of swap can be decidied during process above. anyone can help to
|
b*******e
发帖数: 217 | 6 don't work either. seems also need to track local high. |
b*******e
发帖数: 217 | 7 it is just to show how to find the swapping steps (only swap to the end can
be used to switch the locations)....
【在 g********r 的大作中提到】
: 不需要 真的去swap吧？
: 问题不是去找minimum step吗？
:
: to
|
g********r
发帖数: 58 | 8 真不知道 您在说什么
first round (1) 32 needs swap then step = 2
second round (2) 4 need to swap then step += 1
so step = 3
why we care about how to sort?
【在 b*******e 的大作中提到】
: incorrect.
: see example 3214
: first round (1) 32 needs swap
: get 1432
: second round (2) 4 need to swap
: get 1324
: not sorted.
: I guess needs to use some advanced data structure like stack....
: keep tracking the local min.... then pop us the elements larger than the
: local min and insert them to the end one by one.
|
g********r
发帖数: 58 | 9 SWAP 不是
3214
step1 314 2
step2 14 23
step3 1 234
你是怎么理解的？
can
【在 b*******e 的大作中提到】
: it is just to show how to find the swapping steps (only swap to the end can
: be used to switch the locations)....
|
g********r
发帖数: 58 | 10 SWAP 不是
3214
step1 314 2
step2 14 23
step3 1 234
你是怎么理解的？
can
【在 b*******e 的大作中提到】
: it is just to show how to find the swapping steps (only swap to the end can
: be used to switch the locations)....
|
|
|
b*******e
发帖数: 217 | |
b*******e
发帖数: 217 | 12 I think you are right.....
don't need to know how to swap. yet anyway we know some element needs to be
swapped.
【在 b*******e 的大作中提到】
: how about 231645?
|
b*******e
发帖数: 217 | 13 I think your algorithm is correct:)
【在 g********r 的大作中提到】
: SWAP 不是
: 3214
: step1 314 2
: step2 14 23
: step3 1 234
: 你是怎么理解的？
:
: can
|
y****n
发帖数: 743 | 14 我的思路和你的一样，不过我觉得你的算法有问题。
你的swapMin应该是swap的对吧？
那么if A[i] > swapMin就一定没有数swapMin，
虽然返回时用了stepCnt+1，但怎能保证swapMin只出现一次呢？
needed
swap。
【在 g********r 的大作中提到】
: An operation "swap" means removing an element from the array and appending
: it at the back of the same array. Find the minimum number of "swaps" needed
: to sort that array.
: Eg :- 3124
: Output: 2 (3124->1243->1234)
: 看到版上有人讨论这道题， 总觉得应该有更优解。 而且假设 数字是从 1-n 有些牵强
: 。昨天想到了一个解法，今天又稍稍更新了一下。个人的理解 大家看看有没有错。谢
: 谢！
: 1. 如果数组长度是n，最多就需要swap n－1次，就是每个元素 最多只需要swap一次。
: 我们并不需要关心哪个先哪个后swap。 那么 我们就一个一个元素的判断那些需要swap。
|
y****n
发帖数: 743 | 15 换句话说，当swapMin重复出现时，你的算法会出错。
比如：123332333
【在 y****n 的大作中提到】
: 我的思路和你的一样，不过我觉得你的算法有问题。
: 你的swapMin应该是swap的对吧？
: 那么if A[i] > swapMin就一定没有数swapMin，
: 虽然返回时用了stepCnt+1，但怎能保证swapMin只出现一次呢？
:
: needed
: swap。
|
g********r
发帖数: 58 | 16 嗯 没错， 没考虑到 有重复的情况。
有重复的话， 就需要额外空间了，或者改原数组了。 有没有其他方法？
【在 y****n 的大作中提到】
: 换句话说，当swapMin重复出现时，你的算法会出错。
: 比如：123332333
|
y****n
发帖数: 743 | |
g********r
发帖数: 58 | 18 Got it. Thanks.
看来考虑的还是不够周密啊。这下完美了：）
【在 y****n 的大作中提到】
: 扫描两边就可以了
: http://www.mitbbs.com/article/JobHunting/32344389_0.html
|
