再整搞笑图。 (转载) - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Joke - 肚皮舞运动

再整搞笑图。 (转载)

再整搞笑图。 (转载)# Joke - 肚皮舞运动

n*r2012-11-29 08:11

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)

W*S2012-11-29 08:11

2 楼

我常年带美国歌手到国内演出。国内演出公司一直要求我开辟美国市场，现在有点推辞
不过了，最紧急的有两个项目。在这里问，主要是觉得这里的父母都想让自己的孩子多
了解一下中文和中国文化。
1，这个市类似迪斯尼的大型演出“绿野仙踪”，中文说，英文字幕。道具很多，人也
很多。如果价格便宜，需要演出几十场。这个演出澳大利亚订购了40场，在国内各大剧
场演出过。请大家看看你们有没有兴趣带孩子来看，你们在什么城市。如果你是合适
的人，请直接和我联系具体做一个城市的情况。
http://c.show160.com/330371/trade/a438426
http://v.youku.com/v_show/id_XNjkyOTk0MjM2.html
2，这个项目叫“炎黄之声相声”，有佟有为、马树春，罗峰、张鑫，任一夫、严冒鹏
，管新城。不是一线大家最熟悉的演员，不过他们的演出都很精彩。大家看了一定会乐
开花。
好，请大家投票看看喜欢看哪个，还是都喜欢~~ 你们在哪个城市？
先谢谢大家了！！

n*r2012-11-29 08:11

3 楼

请问有没有人尝试过在南加州的south El Monte提早打指纹？不好意思，好像很多人问
这种问题，希望没有耽误大家的时间。但因为自己只有一天有空,必须要提早打。如果
有成功的案例，心里会踏实点。谢谢~

s*12012-11-29 08:11

4 楼

【以下文字转载自 WaterWorld 讨论区】
发信人: zzbc (甲由田电申旦旧), 信区: WaterWorld
标题: 再整搞笑图。
发信站: BBS 未名空间站 (Thu Nov 29 09:18:05 2012, 美东)

b*u2012-11-29 08:11

5 楼

不用到队尾排序的数字是从1开始的最长有序数组，比如例子里的{1，2}，其余数字都
要依次从队尾重新入列，所以是4-2=2

C*d2012-11-29 08:11

6 楼

有兴趣

【在 W*S 的大作中提到】

: 我常年带美国歌手到国内演出。国内演出公司一直要求我开辟美国市场，现在有点推辞
: 不过了，最紧急的有两个项目。在这里问，主要是觉得这里的父母都想让自己的孩子多
: 了解一下中文和中国文化。
: 1，这个市类似迪斯尼的大型演出“绿野仙踪”，中文说，英文字幕。道具很多，人也
: 很多。如果价格便宜，需要演出几十场。这个演出澳大利亚订购了40场，在国内各大剧
: 场演出过。请大家看看你们有没有兴趣带孩子来看，你们在什么城市。如果你是合适
: 的人，请直接和我联系具体做一个城市的情况。
: http://c.show160.com/330371/trade/a438426
: http://v.youku.com/v_show/id_XNjkyOTk0MjM2.html
: 2，这个项目叫“炎黄之声相声”，有佟有为、马树春，罗峰、张鑫，任一夫、严冒鹏

M*a2012-11-29 08:11

7 楼

有好有一般

p*22012-11-29 08:11

8 楼

这题以前是我贴的吧？

w*w2012-11-29 08:11

9 楼

那个锁很好玩。

r*h2012-11-29 08:11

10 楼

cycle sort?

needed

【在 n****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)

m*n2012-11-29 08:11

11 楼

不错

h*i2012-11-29 08:11

12 楼

inversions and merge sort.

【在 r**h 的大作中提到】

: cycle sort?
:
: needed

f*t2012-11-29 08:11

13 楼

http://www.mitbbs.com/article0/JobHunting/32294603_0.html

p*22012-11-29 08:11

14 楼

记错了。怎么印象中在CF上做过呀

【在 f*******t 的大作中提到】

: http://www.mitbbs.com/article0/JobHunting/32294603_0.html

n*r2012-11-29 08:11

15 楼

学习了！谢谢大神的帮助！

r*h2012-11-29 08:11

16 楼

要是输入是2 1 4 3的话，因为2在1前面，因此
if (array[index] == target)
当target=2时候永远不成立，从而使得minswap = 3，但解是minswap = 2
是我理解错方法了吗

【在 f*******t 的大作中提到】

: http://www.mitbbs.com/article0/JobHunting/32294603_0.html

d*g2012-11-29 08:11

17 楼

我也觉得这个算法不对~

【在 r**h 的大作中提到】

: 要是输入是2 1 4 3的话，因为2在1前面，因此
: if (array[index] == target)
: 当target=2时候永远不成立，从而使得minswap = 3，但解是minswap = 2
: 是我理解错方法了吗

z*p2012-11-29 08:11

18 楼

I think backtou has already given the answer. Let me elaborate it:
-Naive approach: find the smallest element in the array, "swap" it to the
tail; then find the 2nd smallest element, "swap" it to the tail; ...
-Improvement, if the first K elements are already in an increasing order in
the original array, then in the naive approach, we can simply start with the
K+1-th smallest element
-So the minimal number of "swaps" is N-K, where K is the longest prefix of
the sorted array that are already in the right order (they don't have to be
consecutive in the original array--they only have to be in the right order).

needed

【在 n****r 的大作中提到】

f*t2012-11-29 08:11

19 楼

怎样两次能swap成1 2 3 4?

【在 r**h 的大作中提到】

r*h2012-11-29 08:11

20 楼

第一次交换12，第二次交换34？
2143 - 1243 - 1234

【在 f*******t 的大作中提到】

: 怎样两次能swap成1 2 3 4?

f*e2012-11-29 08:11

21 楼

n-(length of maximum consecutively increasing sequence, i.e., 1,2,3,..,i)
for 3124, n = 4, maximum consecutively increasing sequence is 12
thus 4 - 2 =2
for 2134, n = 4, length =1
thus 4 - 1 = 3

needed

【在 n****r 的大作中提到】

f*e2012-11-29 08:11

22 楼

只能加到末尾，

【在 r**h 的大作中提到】

: 第一次交换12，第二次交换34？
: 2143 - 1243 - 1234

c*t2012-11-29 08:11

23 楼

嗯，基本达成共识。
具体怎么解呢？先排序并存到另一个array, 再比较原数组得出longest prefix？
time O(nlgn) space O(n)?

in
the
be
).

【在 z****p 的大作中提到】

: I think backtou has already given the answer. Let me elaborate it:
: -Naive approach: find the smallest element in the array, "swap" it to the
: tail; then find the 2nd smallest element, "swap" it to the tail; ...
: -Improvement, if the first K elements are already in an increasing order in
: the original array, then in the naive approach, we can simply start with the
: K+1-th smallest element
: -So the minimal number of "swaps" is N-K, where K is the longest prefix of
: the sorted array that are already in the right order (they don't have to be
: consecutive in the original array--they only have to be in the right order).
:

f*t2012-11-29 08:11

24 楼

你想输出每次交换的index吗？

【在 c********t 的大作中提到】

: 嗯，基本达成共识。
: 具体怎么解呢？先排序并存到另一个array, 再比较原数组得出longest prefix？
: time O(nlgn) space O(n)?
:
: in
: the
: be
: ).

A*o2012-11-29 08:11

25 楼

May be I am wrong, consider the following ...
Let the unsorted array be V=a_0, a_1, ... a_k, ... a_m
assume min(V)=a_k
'swap' all a_i such that iLet V_1 = a_0 ... a_(k-1)
w.l.g., assume min(V_1) = a_l
Let V_2 = a_(k+1) ... a_m
w.l.g., assume min(V_2) = a_r
Now scan V_2, 'swap' an a_i (k+1<=i<=m), if
(i) a_i > a_r and i < r; OR
(ii)a_i > a_l
O(n) time, O(1) space? :)

【在 c********t 的大作中提到】

: 嗯，基本达成共识。
: 具体怎么解呢？先排序并存到另一个array, 再比较原数组得出longest prefix？
: time O(nlgn) space O(n)?
:
: in
: the
: be
: ).

z*p2012-11-29 08:11

26 楼

I guess this problem is not about algorithm. It asks for the number of min
swaps. It's more like a math problem. As long as we give N-K, our job is
done, and we don't have to implement any algorithm.
Think this problem in another way:
-There is a large graph, where each node is a permutation of the given list
of data; there is an edge points from node i to node j if we can move from
permutation-i to permutation-j by using one "swap".
-Now the question is I pick two nodes i and k in the graph, where k is
special in that its permutation happens to be a sorted list; i is an
arbitrary node.
-Then I ask you "(1) What is length of the min-length path
from i to k in the graph (2) What are exact nodes on the path?"; however,
I didn't ask you to develop an algorithm to find that path, because doing
so may need a sorting first and then a backtrack of path--using that for the
purpose of sorting is not a good idea.

【在 c********t 的大作中提到】

: 嗯，基本达成共识。
: 具体怎么解呢？先排序并存到另一个array, 再比较原数组得出longest prefix？
: time O(nlgn) space O(n)?
:
: in
: the
: be
: ).

c*t2012-11-29 08:11

27 楼

嗨！原来lz忘给原题的重要条件数组是从 1-n的排列啊，搞得我一头雾水。

【在 f*******t 的大作中提到】

: 你想输出每次交换的index吗？

h*i2012-11-29 08:11

28 楼

这个方法好，实现还简单

【在 f*******t 的大作中提到】

: http://www.mitbbs.com/article0/JobHunting/32294603_0.html

b*e2012-11-29 08:11

29 楼

starting from the first element to the last element:
if any element after it is smaller than it, swap this element to the enf of
the array
seems n^2 worst case.

needed

【在 n****r 的大作中提到】

b*e2012-11-29 08:11

30 楼

according to your algorithm for 2134, should be 4-2 = 2 since 34 is the
longest increasing substring.

【在 f*****e 的大作中提到】

: n-(length of maximum consecutively increasing sequence, i.e., 1,2,3,..,i)
: for 3124, n = 4, maximum consecutively increasing sequence is 12
: thus 4 - 2 =2
: for 2134, n = 4, length =1
: thus 4 - 1 = 3
:
: needed

g*r2012-11-29 08:11

31 楼

不用假定数组是1~n的某个排列
O(n) time + 常数 space 的解法－对吗？
int minSwap(int[] A) {
n = len(A)
idxMin = 0
valMin = A[idxMin]
for (int i = 0, i< n, i++)
if valMin > A[i]
valMin = A[i]
idxMin = i
if idxMin == n-1
return n-2
cnt = idxMin
leftMin = INT_MAX
for (int i = 0; i<= idxMin-1 ; i++)
if leftMin < A[i]
leftMin = A[i]
rightMin = A[n-1]
for (int i = n-1; i<= idxMin+1; i-- )
if A[i]> rightMin || A[i] > leftMin
cnt++
if A[i] < rightMin
rightMin = A[i]

return cnt