再论 mini # of swaps to sort array.# JobHunting - 待字闺中
t*u
1 楼
fedex.com/myfedexrewards
up to $50 in total
up to $50 in total
g*r
2 楼
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
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
t*n
3 楼
link 呢
b*e
4 楼
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.
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.
l*y
5 楼
这个网站做的极为粗糙，感觉是假的？
b*e
6 楼
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?
(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?
R*g
7 楼
这是什么阿
b*e
8 楼
don't work either. seems also need to track local high.
a*n
9 楼
g*r
10 楼
不需要 真的去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
问题不是去找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
c*d
11 楼
这个就是fedex reward program的网站
b*e
12 楼
don't work either. seems also need to track local high.
b*e
13 楼
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
be used to switch the locations)....
【在 g********r 的大作中提到】
: 不需要 真的去swap吧？
: 问题不是去找minimum step吗？
:
: to
g*r
14 楼
真不知道 您在说什么
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.
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
15 楼
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)....
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
16 楼
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)....
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
17 楼
how about 231645?
b*e
18 楼
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?
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
19 楼
I think your algorithm is correct:)
【在 g********r 的大作中提到】
: SWAP 不是
: 3214
: step1 314 2
: step2 14 23
: step3 1 234
: 你是怎么理解的？
:
: can
【在 g********r 的大作中提到】
: SWAP 不是
: 3214
: step1 314 2
: step2 14 23
: step3 1 234
: 你是怎么理解的？
:
: can
y*n
20 楼
我的思路和你的一样，不过我觉得你的算法有问题。
你的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。
你的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
21 楼
换句话说，当swapMin重复出现时，你的算法会出错。
比如：123332333
【在 y****n 的大作中提到】
: 我的思路和你的一样，不过我觉得你的算法有问题。
: 你的swapMin应该是swap的对吧？
: 那么if A[i] > swapMin就一定没有数swapMin，
: 虽然返回时用了stepCnt+1，但怎能保证swapMin只出现一次呢？
:
: needed
: swap。
比如：123332333
【在 y****n 的大作中提到】
: 我的思路和你的一样，不过我觉得你的算法有问题。
: 你的swapMin应该是swap的对吧？
: 那么if A[i] > swapMin就一定没有数swapMin，
: 虽然返回时用了stepCnt+1，但怎能保证swapMin只出现一次呢？
:
: needed
: swap。
g*r
22 楼
嗯 没错， 没考虑到 有重复的情况。
有重复的话， 就需要额外空间了，或者改原数组了。 有没有其他方法？
【在 y****n 的大作中提到】
: 换句话说，当swapMin重复出现时，你的算法会出错。
: 比如：123332333
有重复的话， 就需要额外空间了，或者改原数组了。 有没有其他方法？
【在 y****n 的大作中提到】
: 换句话说，当swapMin重复出现时，你的算法会出错。
: 比如：123332333
y*n
23 楼
g*r
24 楼
Got it. Thanks.
看来考虑的还是不够周密啊。这下完美了：）
【在 y****n 的大作中提到】
: 扫描两边就可以了
: http://www.mitbbs.com/article/JobHunting/32344389_0.html
看来考虑的还是不够周密啊。这下完美了：）
【在 y****n 的大作中提到】
: 扫描两边就可以了
: http://www.mitbbs.com/article/JobHunting/32344389_0.html
相关阅读
[LinkedIn][Amazon][Amazon Lab126] 长期提供内推谁给总结一下，U家这一年出了多少抓码？有读law school吗狗家最近team match变慢了吗LIVE: Wikileaks Julian Assange Press Conference 3/23/17 (求一篇wall street journal的文章 (转载)Uber 员工"性福利"现在在ccc，如果回国，签证还能过吗？刷了很多遍题但是拿不到面试怎么办中国人搞machine learning的太多了 (转载)我接触到的台湾人对大陆的感觉分三类。。 (转载)问个问题2013 2014 Infiniti G37 30K mile 人民币 Sunnyvale CA聊点实际的，码农出货量。 (转载)thumbtack 感觉很装逼啊问个unix难题，新手勿入从小公司到大公司降薪跳槽咋样？快到50了，心里很紧张，请问大家觉得50岁在财务和事业上应该是怎样的定位Senior business analyst 在湾区的工资水平最近各种XXX.ai