[BSSD] 忍不住抱怨一下 - 未名空间MITBBS历史存档

c*a2014-02-15 08:02

1 楼

careercup看到A家的题
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)
How to do it less than O(n^2) ?

w*t2014-02-15 08:02

2 楼

每周六带儿子去游泳课，GYM里同时间有2场篮球GAME
儿子游完泳我通常会带他看第一场的下半场，和第二场的上半场
每一场GAME有16个男孩，2场就是32个男孩
所有家长都坐在观众席给孩子们呐喊加油，鼓掌，还有拍照，相互聊天。。。
我这个局外人也不例外
32个孩子里只有一个中国孩子，每次都是爸爸带过来
每一个星期，每一场，这个爸爸都从头到尾低着头玩 IPAD
真不夸张，从来没有见他抬头看一眼儿子
其它的父母没有一个玩手机或者IPAD或任何电子产品
其实作为妈妈，我对体育活动根本没什么兴趣
带儿子上游泳课也好，出去playground玩也好，偶尔也拿手机上网
但绝对大多数时间是盯着孩子的
就算我对别的孩子打球没兴趣，我也很有兴趣看儿子有什么反应
哪怕一个眼神，一个微笑，我知道儿子也能得到鼓励
不知道说什么了，也许我的帖子能给个别父母提个醒

f*d2014-02-15 08:02

3 楼

LIS nlogn

l*a2014-02-15 08:02

4 楼

汗，我带闺女踢球画画体操，都必带ipad...

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

: 每周六带儿子去游泳课，GYM里同时间有2场篮球GAME
: 儿子游完泳我通常会带他看第一场的下半场，和第二场的上半场
: 每一场GAME有16个男孩，2场就是32个男孩
: 所有家长都坐在观众席给孩子们呐喊加油，鼓掌，还有拍照，相互聊天。。。
: 我这个局外人也不例外
: 32个孩子里只有一个中国孩子，每次都是爸爸带过来
: 每一个星期，每一场，这个爸爸都从头到尾低着头玩 IPAD
: 真不夸张，从来没有见他抬头看一眼儿子
: 其它的父母没有一个玩手机或者IPAD或任何电子产品
: 其实作为妈妈，我对体育活动根本没什么兴趣

l*b2014-02-15 08:02

5 楼

貌似是这样，从1开始看第一个i+1 在i 的前面就需要n - i步。大家看对不对
3124 1672345 1263745 14325

N*n2014-02-15 08:02

6 楼

生气！

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

: 每周六带儿子去游泳课，GYM里同时间有2场篮球GAME
: 儿子游完泳我通常会带他看第一场的下半场，和第二场的上半场
: 每一场GAME有16个男孩，2场就是32个男孩
: 所有家长都坐在观众席给孩子们呐喊加油，鼓掌，还有拍照，相互聊天。。。
: 我这个局外人也不例外
: 32个孩子里只有一个中国孩子，每次都是爸爸带过来
: 每一个星期，每一场，这个爸爸都从头到尾低着头玩 IPAD
: 真不夸张，从来没有见他抬头看一眼儿子
: 其它的父母没有一个玩手机或者IPAD或任何电子产品
: 其实作为妈妈，我对体育活动根本没什么兴趣

c*a2014-02-15 08:02

7 楼

能展开说说吗

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

: LIS nlogn

g*s2014-02-15 08:02

8 楼

这有啥抱怨的？没觉得有啥大问题。

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

: 每周六带儿子去游泳课，GYM里同时间有2场篮球GAME
: 儿子游完泳我通常会带他看第一场的下半场，和第二场的上半场
: 每一场GAME有16个男孩，2场就是32个男孩
: 所有家长都坐在观众席给孩子们呐喊加油，鼓掌，还有拍照，相互聊天。。。
: 我这个局外人也不例外
: 32个孩子里只有一个中国孩子，每次都是爸爸带过来
: 每一个星期，每一场，这个爸爸都从头到尾低着头玩 IPAD
: 真不夸张，从来没有见他抬头看一眼儿子
: 其它的父母没有一个玩手机或者IPAD或任何电子产品
: 其实作为妈妈，我对体育活动根本没什么兴趣

f*m2014-02-15 08:02

9 楼

我想需要的swap数目等于n-LIS吧？

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

: LIS nlogn

w*t2014-02-15 08:02

10 楼

个人觉得打篮球GAME，跟画画体操不一样
画画是纯个人作品，有些老师甚至要求家长离场
篮球GAME可不一样，那么多家长在那里吼啊，喊啊，叫好啊，鼓掌啊
孩子之间也是竞技运动，鼓励是很重要的

【在 l******a 的大作中提到】

: 汗，我带闺女踢球画画体操，都必带ipad...

p*22014-02-15 08:02

11 楼

longest increase sequence
2341 需要3步吧

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

: 我想需要的swap数目等于n-LIS吧？

w*t2014-02-15 08:02

12 楼

我重申一下我的观点，玩手机，玩电脑没问题
但每次1.5小时头也不抬的玩，我觉得过了
本来咱中国孩子在篮球队里就显得瘦小，抢不到球

【在 g******s 的大作中提到】

: 这有啥抱怨的？没觉得有啥大问题。

p*22014-02-15 08:02

13 楼

有说是连续得马

【在 l*******b 的大作中提到】

: 貌似是这样，从1开始看第一个i+1 在i 的前面就需要n - i步。大家看对不对
: 3124 : 1672345 : 1263745 : 14325

I*e2014-02-15 08:02

14 楼

我们coach不让家长当场外指导
可以鼓掌

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

: 个人觉得打篮球GAME，跟画画体操不一样
: 画画是纯个人作品，有些老师甚至要求家长离场
: 篮球GAME可不一样，那么多家长在那里吼啊，喊啊，叫好啊，鼓掌啊
: 孩子之间也是竞技运动，鼓励是很重要的

p*22014-02-15 08:02

15 楼

require 'set'
def swapsort(arr)
sorted=arr.sort
pos={}
sorted.each_with_index {|num, i| pos[num]=i}
set=Set.new
ret=0
curr=nil
arr.each do |num|
set<if pos[num]nil? || numret=arr.length-pos[num]-1
curr=num
end
end
ret
end

w*t2014-02-15 08:02

16 楼

不用指导战术吧？那是教练的事，可以呐喊鼓励啊

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

: 我们coach不让家长当场外指导
: 可以鼓掌

l*b2014-02-15 08:02

17 楼

算步数的话感觉不需要记录所有已出现的元素。记录最小的一个即可

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

: require 'set'
: def swapsort(arr)
: sorted=arr.sort
: pos={}
: sorted.each_with_index {|num, i| pos[num]=i}
: set=Set.new
: ret=0
: curr=nil
: arr.each do |num|
: set<

R*i2014-02-15 08:02

18 楼

汗一个，我经常在一边上班...有一个晚上我们组三个妈妈加班，一个在游泳池，一个
在篮球场，我在体操房。那两个一个一白人一个印度第二代移民。

c*a2014-02-15 08:02

19 楼

二爷能发个java,c++类吗...
这语言太高级了，有些syntax我跪了

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

: require 'set'
: def swapsort(arr)
: sorted=arr.sort
: pos={}
: sorted.each_with_index {|num, i| pos[num]=i}
: set=Set.new
: ret=0
: curr=nil
: arr.each do |num|
: set<

X*r2014-02-15 08:02

20 楼

不觉得有什么问题。你自己认为和孩子的互动投入程度应该有多少，不代表别人不同的
投入程度都是不合理的。

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

: 每周六带儿子去游泳课，GYM里同时间有2场篮球GAME
: 儿子游完泳我通常会带他看第一场的下半场，和第二场的上半场
: 每一场GAME有16个男孩，2场就是32个男孩
: 所有家长都坐在观众席给孩子们呐喊加油，鼓掌，还有拍照，相互聊天。。。
: 我这个局外人也不例外
: 32个孩子里只有一个中国孩子，每次都是爸爸带过来
: 每一个星期，每一场，这个爸爸都从头到尾低着头玩 IPAD
: 真不夸张，从来没有见他抬头看一眼儿子
: 其它的父母没有一个玩手机或者IPAD或任何电子产品
: 其实作为妈妈，我对体育活动根本没什么兴趣

p*22014-02-15 08:02

21 楼

你是说哪一段？

【在 l*******b 的大作中提到】

: 算步数的话感觉不需要记录所有已出现的元素。记录最小的一个即可

b*i2014-02-15 08:02

22 楼

是的，孩子打比赛的时候还是最好有个亲友团声援的气势的。
不过体操课时候我也是躲得远远的自己玩爱拍，要不小娃总看我。
就这样还时不时满场听到老师大叫我儿子的名字

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

: 个人觉得打篮球GAME，跟画画体操不一样
: 画画是纯个人作品，有些老师甚至要求家长离场
: 篮球GAME可不一样，那么多家长在那里吼啊，喊啊，叫好啊，鼓掌啊
: 孩子之间也是竞技运动，鼓励是很重要的

p*22014-02-15 08:02

23 楼

就是 luckynoob的算法。但是我做的是数字不连续的。如果连续的就要容易些。

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

:
: 二爷能发个java,c++类吗...
: 这语言太高级了，有些syntax我跪了

l*r2014-02-15 08:02

24 楼

玩candy crush的飘过~~~

l*b2014-02-15 08:02

25 楼

def swapEndSort(a: List[Int]) = {
val b = a.zipWithIndex.sortWith(_._1 < _._1).zipWithIndex
val i = b.sliding(2).find(x => x(0)._1._2 > x(1)._1._2)
if(i.isEmpty) 0
else a.length - i.get(0)._2 - 1
}
scala里有些操作list的方法挺好用的，比c++里面强大许多，值得一学

g*o2014-02-15 08:02

26 楼

嗯我也觉得不太合适
but what can you do

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

: 每周六带儿子去游泳课，GYM里同时间有2场篮球GAME
: 儿子游完泳我通常会带他看第一场的下半场，和第二场的上半场
: 每一场GAME有16个男孩，2场就是32个男孩
: 所有家长都坐在观众席给孩子们呐喊加油，鼓掌，还有拍照，相互聊天。。。
: 我这个局外人也不例外
: 32个孩子里只有一个中国孩子，每次都是爸爸带过来
: 每一个星期，每一场，这个爸爸都从头到尾低着头玩 IPAD
: 真不夸张，从来没有见他抬头看一眼儿子
: 其它的父母没有一个玩手机或者IPAD或任何电子产品
: 其实作为妈妈，我对体育活动根本没什么兴趣

p*22014-02-15 08:02

27 楼

val i = b.sliding(2).find(x => x(0)._1._2 > x(1)._1._2)
这句话复杂度多少？

【在 l*******b 的大作中提到】

: def swapEndSort(a: List[Int]) = {
: val b = a.zipWithIndex.sortWith(_._1 < _._1).zipWithIndex
: val i = b.sliding(2).find(x => x(0)._1._2 > x(1)._1._2)
: if(i.isEmpty) 0
: else a.length - i.get(0)._2 - 1
: }
: scala里有些操作list的方法挺好用的，比c++里面强大许多，值得一学

l*e2014-02-15 08:02

28 楼

没啥啦，反正有人帮加油。。。不过爹妈表明一个态度还是有帮助的。。。还有，难道
大家都不把孩子的比赛录下来回去分析的吗，不然怎么进步呢？//run

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

: 每周六带儿子去游泳课，GYM里同时间有2场篮球GAME
: 儿子游完泳我通常会带他看第一场的下半场，和第二场的上半场
: 每一场GAME有16个男孩，2场就是32个男孩
: 所有家长都坐在观众席给孩子们呐喊加油，鼓掌，还有拍照，相互聊天。。。
: 我这个局外人也不例外
: 32个孩子里只有一个中国孩子，每次都是爸爸带过来
: 每一个星期，每一场，这个爸爸都从头到尾低着头玩 IPAD
: 真不夸张，从来没有见他抬头看一眼儿子
: 其它的父母没有一个玩手机或者IPAD或任何电子产品
: 其实作为妈妈，我对体育活动根本没什么兴趣

l*b2014-02-15 08:02

29 楼

线性的，照着list一个一个往前找

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

:
: val i = b.sliding(2).find(x => x(0)._1._2 > x(1)._1._2)
: 这句话复杂度多少？

b*i2014-02-15 08:02

30 楼

the best thing she can do is 发包子

【在 g*****o 的大作中提到】

: 嗯我也觉得不太合适
: but what can you do

s*12014-02-15 08:02

31 楼

这题BFS行不行？
3124 有3个adjacent node
1243,3241,3142,
然后再BFS下去，
当然最好还有个hash table,因为可能之前出现过的会再次出现，如果再次出现的话，
Queue就不放进去了

V*82014-02-15 08:02

32 楼

说不定家里有其他孩子，女的带女儿，男的带儿子。
眼不见心不烦，要给别人带，就不要不满意啊提意见啊抱怨了。。。不然自己上。

c*a2014-02-15 08:02

33 楼

我照着luckynoob的算法写了出来...跑了几个test都正确...我不懂这算法啊
public static int numOfSwap(int[]ar){
List unorder = new ArrayList();
for(int i =0;iif(i+1ar[i+1])
unorder.add(ar[i]);
}
Collections.sort(unorder);
int biggestUnorder = unorder.get(unorder.size()-1);
if(biggestUnorder > ar[ar.length-1])
return biggestUnorder - ar[ar.length-1];
int smallestUnorder = unorder.get(0);
for(int i = ar.length-1;i>=0;i--){
if(smallestUnorder>ar[i])
return ar[i+1]-ar[i];
}
return -1;
}

g*o2014-02-15 08:02

34 楼

咦这会儿想起来包子是啥啦
这个症状很像强迫性间歇性失忆啊～～

【在 b********i 的大作中提到】

: the best thing she can do is 发包子

f*m2014-02-15 08:02

35 楼

哦，我弄错了。

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

: longest increase sequence
: 2341 需要3步吧

b*i2014-02-15 08:02

36 楼

除了我这么市侩俗气的人，还有人提到过包子吗。。？

【在 g*****o 的大作中提到】

: 咦这会儿想起来包子是啥啦
: 这个症状很像强迫性间歇性失忆啊～～

l*b2014-02-15 08:02

37 楼

数出来的是不需要动的。一旦动了i+1大小的元素，这个元素就被插到最后了。比它大
的必须都重新插入到最后

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

: 我照着luckynoob的算法写了出来...跑了几个test都正确...我不懂这算法啊
: public static int numOfSwap(int[]ar){
: List unorder = new ArrayList();
: for(int i =0;i: if(i+1ar[i+1])
: unorder.add(ar[i]);
: }
: Collections.sort(unorder);
: int biggestUnorder = unorder.get(unorder.size()-1);
: if(biggestUnorder > ar[ar.length-1])

r*i2014-02-15 08:02

38 楼

我娃就强烈要求我在她练习的时候看着她。虽然我不在的时候她也练得挺好的。我去大
部分时间就是为了录像，还有就是找教练交流一下。

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

: 没啥啦，反正有人帮加油。。。不过爹妈表明一个态度还是有帮助的。。。还有，难道
: 大家都不把孩子的比赛录下来回去分析的吗，不然怎么进步呢？//run

j*y2014-02-15 08:02

39 楼

那比如 4 3 2 1. 第一个 i + 1 在 i的前面的 i = 3, 4 在 3 前面, 这个就好像不
对了阿。

【在 l*******b 的大作中提到】

: 貌似是这样，从1开始看第一个i+1 在i 的前面就需要n - i步。大家看对不对
: 3124 : 1672345 : 1263745 : 14325

r*i2014-02-15 08:02

40 楼

送儿子去练体操的很少啊。

【在 b********i 的大作中提到】

: 是的，孩子打比赛的时候还是最好有个亲友团声援的气势的。
: 不过体操课时候我也是躲得远远的自己玩爱拍，要不小娃总看我。
: 就这样还时不时满场听到老师大叫我儿子的名字

p*22014-02-15 08:02

41 楼

要找最小的。找到4,3还要继续往下找。

【在 j*****y 的大作中提到】

: 那比如 4 3 2 1. 第一个 i + 1 在 i的前面的 i = 3, 4 在 3 前面, 这个就好像不
: 对了阿。

l*r2014-02-15 08:02

42 楼

能每次都带娃去也不错了。

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

: 每周六带儿子去游泳课，GYM里同时间有2场篮球GAME
: 儿子游完泳我通常会带他看第一场的下半场，和第二场的上半场
: 每一场GAME有16个男孩，2场就是32个男孩
: 所有家长都坐在观众席给孩子们呐喊加油，鼓掌，还有拍照，相互聊天。。。
: 我这个局外人也不例外
: 32个孩子里只有一个中国孩子，每次都是爸爸带过来
: 每一个星期，每一场，这个爸爸都从头到尾低着头玩 IPAD
: 真不夸张，从来没有见他抬头看一眼儿子
: 其它的父母没有一个玩手机或者IPAD或任何电子产品
: 其实作为妈妈，我对体育活动根本没什么兴趣

c*t2014-02-15 08:02

43 楼

scala确实很酷，感觉以后会一统江湖

【在 l*******b 的大作中提到】

: def swapEndSort(a: List[Int]) = {
: val b = a.zipWithIndex.sortWith(_._1 < _._1).zipWithIndex
: val i = b.sliding(2).find(x => x(0)._1._2 > x(1)._1._2)
: if(i.isEmpty) 0
: else a.length - i.get(0)._2 - 1
: }
: scala里有些操作list的方法挺好用的，比c++里面强大许多，值得一学

l*r2014-02-15 08:02

44 楼

说不定那个爸爸是他家娃足球队/棒球队的教练，正在ipad上仔细研究娃的足球/棒球录
像。篮球只是来随便玩玩而已。:)

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

: 没啥啦，反正有人帮加油。。。不过爹妈表明一个态度还是有帮助的。。。还有，难道
: 大家都不把孩子的比赛录下来回去分析的吗，不然怎么进步呢？//run

l*b2014-02-15 08:02

45 楼

一统江湖估计不行，实用的functional programming总觉得值得学一下，好多概念不太
一样
haskell 总觉得离能用得上比较远，有个xmonad窗口管理器，很有意思。Scala 的包装
和c之类的还挺接近的，可能好学点

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

: scala确实很酷，感觉以后会一统江湖

b*i2014-02-15 08:02

46 楼

这么小的小屁孩子，谈不上练，就是找个他喜欢的老师和地方，聚众玩闹。。
我打算照着奥运项目列表，他们十岁前都给他们过一遍。。。
射击和马术好像难点儿哈。。。一个举不动枪，一个够不着马镫子。。

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

: 送儿子去练体操的很少啊。

f*t2014-02-15 08:02

47 楼

O(N)解思路是：
（首先假定数组是1~n的某个排列，如果是随便取一堆不重复的数字排序后也可以做，
复杂度会升至O(NlogN)，空间额外消耗O(N)）
以3, 1, 2, 4为例，首先要找的是最小的数字，也就是1，在它前面的数字全部需要移
到后面。所以1的index是几，就要移动几次。
找到1以后再找2，如果2刚好在1的后面，那么我们不用移它，否则1与2之间有几个数，
我们就要移几次。
依此类推，扫描一遍数组即能得出答案。
public int minSwap(int[] array) {
if (array == null || array.length < 2)
return 0;

int minSwap = 0;
int target = 1, index = 0;
while (index < array.length) {
if (array[index] == target) {
index++;
target++;
} else {
minSwap++;
index++;
}
}

return minSwap;
}

r*i2014-02-15 08:02

48 楼

这个太AMBICIOUS了，还有跳水皮划艇帆船都不好找场地啊。

【在 b********i 的大作中提到】

: 这么小的小屁孩子，谈不上练，就是找个他喜欢的老师和地方，聚众玩闹。。
: 我打算照着奥运项目列表，他们十岁前都给他们过一遍。。。
: 射击和马术好像难点儿哈。。。一个举不动枪，一个够不着马镫子。。

w*o2014-02-15 08:02

49 楼

luckynoob的算法是对的。
具体实现可以这样：
1。对原数组排序，不过排序结果是index而不是value，比如：[4，3，2，1]排序后得
到[3，2，1，0]，[2，3，7，4]排序后得到[0，1，3，2]
2。对index数组找到第一个降序元素的index i，比如[3，2，1，0]是1，[0，1，3，2]
是3
3。返回n-i

C*e2014-02-15 08:02

50 楼

说的好。我要找老公算账。

l*b2014-02-15 08:02

51 楼

nice one!

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

: O(N)解思路是：
: （首先假定数组是1~n的某个排列，如果是随便取一堆不重复的数字排序后也可以做，
: 复杂度会升至O(NlogN)，空间额外消耗O(N)）
: 以3, 1, 2, 4为例，首先要找的是最小的数字，也就是1，在它前面的数字全部需要移
: 到后面。所以1的index是几，就要移动几次。
: 找到1以后再找2，如果2刚好在1的后面，那么我们不用移它，否则1与2之间有几个数，
: 我们就要移几次。
: 依此类推，扫描一遍数组即能得出答案。
: public int minSwap(int[] array) {
: if (array == null || array.length < 2)

w*e2014-02-15 08:02

52 楼

同意你！

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

: 个人觉得打篮球GAME，跟画画体操不一样
: 画画是纯个人作品，有些老师甚至要求家长离场
: 篮球GAME可不一样，那么多家长在那里吼啊，喊啊，叫好啊，鼓掌啊
: 孩子之间也是竞技运动，鼓励是很重要的

b*e2014-02-15 08:02

53 楼

如果是随便取一堆不重复的数字排序后也可以?
what do you mean """排序后""""也可以做

w*e2014-02-15 08:02

54 楼

这个，不会是你老公吧。。。

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

: 说的好。我要找老公算账。

y*n2014-02-15 08:02

55 楼

你的思路是对的，算法是有问题的。
比如：1, 2, 1, 2
只需swap一次，你的算法返回2。
我找到的方法和你的几乎一样，只是需要扫描两遍。

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

: O(N)解思路是：
: （首先假定数组是1~n的某个排列，如果是随便取一堆不重复的数字排序后也可以做，
: 复杂度会升至O(NlogN)，空间额外消耗O(N)）
: 以3, 1, 2, 4为例，首先要找的是最小的数字，也就是1，在它前面的数字全部需要移
: 到后面。所以1的index是几，就要移动几次。
: 找到1以后再找2，如果2刚好在1的后面，那么我们不用移它，否则1与2之间有几个数，
: 我们就要移几次。
: 依此类推，扫描一遍数组即能得出答案。
: public int minSwap(int[] array) {
: if (array == null || array.length < 2)

s*j2014-02-15 08:02

56 楼

mind your own shit.

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

: 每周六带儿子去游泳课，GYM里同时间有2场篮球GAME
: 儿子游完泳我通常会带他看第一场的下半场，和第二场的上半场
: 每一场GAME有16个男孩，2场就是32个男孩
: 所有家长都坐在观众席给孩子们呐喊加油，鼓掌，还有拍照，相互聊天。。。
: 我这个局外人也不例外
: 32个孩子里只有一个中国孩子，每次都是爸爸带过来
: 每一个星期，每一场，这个爸爸都从头到尾低着头玩 IPAD
: 真不夸张，从来没有见他抬头看一眼儿子
: 其它的父母没有一个玩手机或者IPAD或任何电子产品
: 其实作为妈妈，我对体育活动根本没什么兴趣

y*n2014-02-15 08:02

57 楼

这道题如果数组内容是杂乱的有重复依然可以O(N)搞定。

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

: O(N)解思路是：
: （首先假定数组是1~n的某个排列，如果是随便取一堆不重复的数字排序后也可以做，
: 复杂度会升至O(NlogN)，空间额外消耗O(N)）
: 以3, 1, 2, 4为例，首先要找的是最小的数字，也就是1，在它前面的数字全部需要移
: 到后面。所以1的index是几，就要移动几次。
: 找到1以后再找2，如果2刚好在1的后面，那么我们不用移它，否则1与2之间有几个数，
: 我们就要移几次。
: 依此类推，扫描一遍数组即能得出答案。
: public int minSwap(int[] array) {
: if (array == null || array.length < 2)

w*t2014-02-15 08:02

58 楼

看体型就知道不可能，恩

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

: 说不定那个爸爸是他家娃足球队/棒球队的教练，正在ipad上仔细研究娃的足球/棒球录
: 像。篮球只是来随便玩玩而已。:)

y*n2014-02-15 08:02

59 楼

思路：
1. 逆序遍历，凡是比后面最小值min大的元素，都需要swap。
并且记录其中最小值swapMin。
2. 再次逆序遍历，把第一次没数过的并且比swapMin大的都需要swap。
假设输入参数不为空：
public static int MinSwap(int[] arr)
{
int swapCount = 0;
int swapMin = int.MaxValue;
int min = int.MaxValue;
for (int i = arr.Length - 1; i >= 0; i--)
if (arr[i] > min)
{
swapCount++;
if (arr[i] < swapMin)
swapMin = arr[i];
}
else if (arr[i] < min)
min = arr[i];
min = int.MaxValue;
for (int i = arr.Length - 1; i >= 0; i--)
{
if ((arr[i] <= min) && (arr[i] > swapMin))
swapCount++;
if (arr[i] < min)
min = arr[i];
}
return swapCount;
}

w*t2014-02-15 08:02

60 楼

你的POINT是什么？
女的带女儿，男的带儿子，所以就不用认真带？
你第二句话就更莫名其妙了

【在 V*****8 的大作中提到】

: 说不定家里有其他孩子，女的带女儿，男的带儿子。
: 眼不见心不烦，要给别人带，就不要不满意啊提意见啊抱怨了。。。不然自己上。

c*a2014-02-15 08:02

61 楼

careercup看到A家的题
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)
How to do it less than O(n^2) ?

w*e2014-02-15 08:02

62 楼

瞎说一句啊，你如果没有一个半小时盯着人家看，那你不能宣称人家一次头都没抬。

l*b2014-02-15 08:02

63 楼

貌似是这样，从1开始看第一个i+1 在i 的前面就需要n - i步。大家看对不对
3124 1672345 1263745 14325

V*82014-02-15 08:02

64 楼

我的point是，谁带谁做主。
不带的那方就不要诸多要求了，比如那个男的老婆如果看到这个帖子，回去吵了闹了，
那就自己上，自己周末带儿子去打篮球，和男方换换位置，那到时候她想怎么吆喝呐喊
都可以喊个够了。
如果因为种种原因不能自己上，就别管男的怎么带了，反正自己也带不了。

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

: 你的POINT是什么？
: 女的带女儿，男的带儿子，所以就不用认真带？
: 你第二句话就更莫名其妙了

c*a2014-02-15 08:02

65 楼

能展开说说吗

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

: LIS nlogn

V*82014-02-15 08:02

66 楼

我最烦不干活还在旁边指手画脚诸多要求的人，看不惯可以自己上嘛。

f*m2014-02-15 08:02

67 楼

我想需要的swap数目等于n-LIS吧？

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

: LIS nlogn

n*a2014-02-15 08:02

68 楼

我带儿子去空手道课，要么跟人聊天要么ipad，基本也不看儿子。
我觉得很多家长都这样啊

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

: 每周六带儿子去游泳课，GYM里同时间有2场篮球GAME
: 儿子游完泳我通常会带他看第一场的下半场，和第二场的上半场
: 每一场GAME有16个男孩，2场就是32个男孩
: 所有家长都坐在观众席给孩子们呐喊加油，鼓掌，还有拍照，相互聊天。。。
: 我这个局外人也不例外
: 32个孩子里只有一个中国孩子，每次都是爸爸带过来
: 每一个星期，每一场，这个爸爸都从头到尾低着头玩 IPAD
: 真不夸张，从来没有见他抬头看一眼儿子
: 其它的父母没有一个玩手机或者IPAD或任何电子产品
: 其实作为妈妈，我对体育活动根本没什么兴趣

p*22014-02-15 08:02

69 楼

longest increase sequence
2341 需要3步吧

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

: 我想需要的swap数目等于n-LIS吧？

s*e2014-02-15 08:02

70 楼

呵呵，LZ的意思我理解，足球篮球之类的运动一般家长还是会在一边喝彩加油的啊。
空手道我不清楚，但是体操舞蹈游泳什么的不看挺正常的，好多老师甚至不让看。

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

: 我带儿子去空手道课，要么跟人聊天要么ipad，基本也不看儿子。
: 我觉得很多家长都这样啊

p*22014-02-15 08:02

71 楼

有说是连续得马

【在 l*******b 的大作中提到】

: 貌似是这样，从1开始看第一个i+1 在i 的前面就需要n - i步。大家看对不对
: 3124 : 1672345 : 1263745 : 14325

r*i2014-02-15 08:02

72 楼

体操舞蹈最后RECITAL的时候，家长有机会看到。游泳肯定可以看，但是加油鼓劲用处
不大。
空手道SPARRING的时候会比较好看，练FORM之类的比较枯燥，翻来覆去就那么几招，家
长看着也兴趣不大。

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

: 呵呵，LZ的意思我理解，足球篮球之类的运动一般家长还是会在一边喝彩加油的啊。
: 空手道我不清楚，但是体操舞蹈游泳什么的不看挺正常的，好多老师甚至不让看。

p*22014-02-15 08:02

73 楼

require 'set'
def swapsort(arr)
sorted=arr.sort
pos={}
sorted.each_with_index {|num, i| pos[num]=i}
set=Set.new
ret=0
curr=nil
arr.each do |num|
set<if pos[num]nil? || numret=arr.length-pos[num]-1
curr=num
end
end
ret
end

w*t2014-02-15 08:02

74 楼

我觉得有些id没明白。
我指的是这种篮球的game
不是平时教练教他们怎么拍球
虽然不是什么大的比赛
但篮球这种东西就是在竞技过程中得到经验和学习
楼上说的那些活动
周边有其他的父母全都在呐喊助威鼓掌吗？
如果其他的父母都在这样做
你还会一个人低着头看iPad的吗？

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

: 呵呵，LZ的意思我理解，足球篮球之类的运动一般家长还是会在一边喝彩加油的啊。
: 空手道我不清楚，但是体操舞蹈游泳什么的不看挺正常的，好多老师甚至不让看。

l*b2014-02-15 08:02

75 楼

算步数的话感觉不需要记录所有已出现的元素。记录最小的一个即可

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

: require 'set'
: def swapsort(arr)
: sorted=arr.sort
: pos={}
: sorted.each_with_index {|num, i| pos[num]=i}
: set=Set.new
: ret=0
: curr=nil
: arr.each do |num|
: set<

w*t2014-02-15 08:02

76 楼

你说的，跟我说的无关。
我不是这个人的老婆
还有，他们要么就是两个孩子分别带
要么女的就是在家做家务，做饭
你难道以为女方在家是闲着的吗？
再说一遍那个是在打game，不是平时的训练

【在 V*****8 的大作中提到】

: 我的point是，谁带谁做主。
: 不带的那方就不要诸多要求了，比如那个男的老婆如果看到这个帖子，回去吵了闹了，
: 那就自己上，自己周末带儿子去打篮球，和男方换换位置，那到时候她想怎么吆喝呐喊
: 都可以喊个够了。
: 如果因为种种原因不能自己上，就别管男的怎么带了，反正自己也带不了。

c*a2014-02-15 08:02

77 楼

二爷能发个java,c++类吗...
这语言太高级了，有些syntax我跪了

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

: require 'set'
: def swapsort(arr)
: sorted=arr.sort
: pos={}
: sorted.each_with_index {|num, i| pos[num]=i}
: set=Set.new
: ret=0
: curr=nil
: arr.each do |num|
: set<

w*t2014-02-15 08:02

78 楼

周边有其他的父母全都在呐喊助威鼓掌吗？
如果其他的父母都在这样做
你还会一个人低着头看iPad吗
我已经说过了那里所有的家长全都在鼓掌呐威

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

: 我带儿子去空手道课，要么跟人聊天要么ipad，基本也不看儿子。
: 我觉得很多家长都这样啊

p*22014-02-15 08:02

79 楼

你是说哪一段？

【在 l*******b 的大作中提到】

: 算步数的话感觉不需要记录所有已出现的元素。记录最小的一个即可

N*n2014-02-15 08:02

80 楼

每个人心里孩子的分量是不一样的，算了。

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

: 周边有其他的父母全都在呐喊助威鼓掌吗？
: 如果其他的父母都在这样做
: 你还会一个人低着头看iPad吗
: 我已经说过了那里所有的家长全都在鼓掌呐威

p*22014-02-15 08:02

81 楼

就是 luckynoob的算法。但是我做的是数字不连续的。如果连续的就要容易些。

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

:
: 二爷能发个java,c++类吗...
: 这语言太高级了，有些syntax我跪了

w*82014-02-15 08:02

82 楼

空手道不一样啊，只是上课而己，又不用加油助威的。蓝球，足球，冰球的比赛少有家
长不看的。我孩子的比赛我和我LG都看的很投入，这种时候连两岁的弟弟都顾不上管，
只要不跑走，爱干什么干什么

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

: 我带儿子去空手道课，要么跟人聊天要么ipad，基本也不看儿子。
: 我觉得很多家长都这样啊

l*b2014-02-15 08:02

83 楼

def swapEndSort(a: List[Int]) = {
val b = a.zipWithIndex.sortWith(_._1 < _._1).zipWithIndex
val i = b.sliding(2).find(x => x(0)._1._2 > x(1)._1._2)
if(i.isEmpty) 0
else a.length - i.get(0)._2 - 1
}
scala里有些操作list的方法挺好用的，比c++里面强大许多，值得一学

R*C2014-02-15 08:02

84 楼

我想可能这比赛每周都有,做父亲的已经麻木了,本身估计也不爱运动,只当完成任务。
。。。

p*22014-02-15 08:02

85 楼

val i = b.sliding(2).find(x => x(0)._1._2 > x(1)._1._2)
这句话复杂度多少？

【在 l*******b 的大作中提到】

: def swapEndSort(a: List[Int]) = {
: val b = a.zipWithIndex.sortWith(_._1 < _._1).zipWithIndex
: val i = b.sliding(2).find(x => x(0)._1._2 > x(1)._1._2)
: if(i.isEmpty) 0
: else a.length - i.get(0)._2 - 1
: }
: scala里有些操作list的方法挺好用的，比c++里面强大许多，值得一学

h*y2014-02-15 08:02

86 楼

我觉得有以下几种可能。
1.爸爸本身不感兴趣。也有些内向。。但是能按时接送孩子也算很不错了。。
2.这种活动太多了。。喊腻了。。。
3.快考试了。。忙着复习。。。（我LD就这情况。送女儿跳舞时候。。他就坐那埋头做
作业复习课）
4.保姆接送（爸爸妈妈工作忙。没时间。。。雇佣的司机过去送孩子的。。。不热情
也正常）
5.忙这工作？加班？处理信件？

l*b2014-02-15 08:02

87 楼

线性的，照着list一个一个往前找

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

:
: val i = b.sliding(2).find(x => x(0)._1._2 > x(1)._1._2)
: 这句话复杂度多少？

h*e2014-02-15 08:02

88 楼

1，作为爸爸能每次带孩子比赛，已经算难得了的，需要鼓励。
2，作为全场唯一一个中国家长，估计家长里没有他什么朋友可以一起看球聊天的，所
以无聊看IPAD。
3，也许他以前看孩子打过，现在看腻了。
我儿子刚开始踢球那年我也经常看，后来看的就少了，经常自己去锻炼。
中国人在美国没有七大姑八大姨的亲戚朋友帮着呐喊助威，这方面是要差一些，要不你
下回坐他旁边跟他聊天儿看球，为他儿子呐喊。有了这个氛围他也许对看球会感兴趣起
来，也说不定给你儿子找个playdate的大伙伴。

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

: 每周六带儿子去游泳课，GYM里同时间有2场篮球GAME
: 儿子游完泳我通常会带他看第一场的下半场，和第二场的上半场
: 每一场GAME有16个男孩，2场就是32个男孩
: 所有家长都坐在观众席给孩子们呐喊加油，鼓掌，还有拍照，相互聊天。。。
: 我这个局外人也不例外
: 32个孩子里只有一个中国孩子，每次都是爸爸带过来
: 每一个星期，每一场，这个爸爸都从头到尾低着头玩 IPAD
: 真不夸张，从来没有见他抬头看一眼儿子
: 其它的父母没有一个玩手机或者IPAD或任何电子产品
: 其实作为妈妈，我对体育活动根本没什么兴趣

s*12014-02-15 08:02

89 楼

这题BFS行不行？
3124 有3个adjacent node
1243,3241,3142,
然后再BFS下去，
当然最好还有个hash table,因为可能之前出现过的会再次出现，如果再次出现的话，
Queue就不放进去了

h*e2014-02-15 08:02

90 楼

小声说，也许，这个爸爸耳朵比较背呢，或者是聋哑人。。。run...

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

: 周边有其他的父母全都在呐喊助威鼓掌吗？
: 如果其他的父母都在这样做
: 你还会一个人低着头看iPad吗
: 我已经说过了那里所有的家长全都在鼓掌呐威

c*a2014-02-15 08:02

91 楼

我照着luckynoob的算法写了出来...跑了几个test都正确...我不懂这算法啊
public static int numOfSwap(int[]ar){
List unorder = new ArrayList();
for(int i =0;iif(i+1ar[i+1])
unorder.add(ar[i]);
}
Collections.sort(unorder);
int biggestUnorder = unorder.get(unorder.size()-1);
if(biggestUnorder > ar[ar.length-1])
return biggestUnorder - ar[ar.length-1];
int smallestUnorder = unorder.get(0);
for(int i = ar.length-1;i>=0;i--){
if(smallestUnorder>ar[i])
return ar[i+1]-ar[i];
}
return -1;
}

h*y2014-02-15 08:02

92 楼

我自己带女儿跳舞的时候也是一声不吭。。。。不过我内心还是很关注的。。。。汗。
。。

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

: 1，作为爸爸能每次带孩子比赛，已经算难得了的，需要鼓励。
: 2，作为全场唯一一个中国家长，估计家长里没有他什么朋友可以一起看球聊天的，所
: 以无聊看IPAD。
: 3，也许他以前看孩子打过，现在看腻了。
: 我儿子刚开始踢球那年我也经常看，后来看的就少了，经常自己去锻炼。
: 中国人在美国没有七大姑八大姨的亲戚朋友帮着呐喊助威，这方面是要差一些，要不你
: 下回坐他旁边跟他聊天儿看球，为他儿子呐喊。有了这个氛围他也许对看球会感兴趣起
: 来，也说不定给你儿子找个playdate的大伙伴。

f*m2014-02-15 08:02

93 楼

哦，我弄错了。

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

: longest increase sequence
: 2341 需要3步吧

w*t2014-02-15 08:02

94 楼

主要是形成了一个鲜明的对比，乌泱泱坐满了家长，只有他一个人低头玩电脑
是IPAD，所以我不认为是在工作，手指频率来看，估计是打游戏
全场唯一一个中国孩子，我还是多关注的
戴眼镜，个子不高，也抢不到什么球，基本就是外围跟着别人跑而已
每次看到那孩子往看台上瞄的时候，我就有点心疼
打得不好可能更需要父亲的鼓励吧
实际上我LD说这个孩子应该考虑退出
父亲不上心篮球，打球的时候又被打击自信心

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

: 1，作为爸爸能每次带孩子比赛，已经算难得了的，需要鼓励。
: 2，作为全场唯一一个中国家长，估计家长里没有他什么朋友可以一起看球聊天的，所
: 以无聊看IPAD。
: 3，也许他以前看孩子打过，现在看腻了。
: 我儿子刚开始踢球那年我也经常看，后来看的就少了，经常自己去锻炼。
: 中国人在美国没有七大姑八大姨的亲戚朋友帮着呐喊助威，这方面是要差一些，要不你
: 下回坐他旁边跟他聊天儿看球，为他儿子呐喊。有了这个氛围他也许对看球会感兴趣起
: 来，也说不定给你儿子找个playdate的大伙伴。

l*b2014-02-15 08:02

95 楼

数出来的是不需要动的。一旦动了i+1大小的元素，这个元素就被插到最后了。比它大
的必须都重新插入到最后

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

: 我照着luckynoob的算法写了出来...跑了几个test都正确...我不懂这算法啊
: public static int numOfSwap(int[]ar){
: List unorder = new ArrayList();
: for(int i =0;i: if(i+1ar[i+1])
: unorder.add(ar[i]);
: }
: Collections.sort(unorder);
: int biggestUnorder = unorder.get(unorder.size()-1);
: if(biggestUnorder > ar[ar.length-1])

w*b2014-02-15 08:02

96 楼

中国家长应该多给孩子鼓励，小孩都特别希望父母能注意他们的表现。我女儿从小到大
无论玩什么，我都拍手叫好，弄得她玩什么都自信满棚，人有自信就能越玩越好。她七
岁时我跟她赛跑，我把速度控制在一起到达终点，然后说you win!，她一脸大度的表情
说，we tie.

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

: 主要是形成了一个鲜明的对比，乌泱泱坐满了家长，只有他一个人低头玩电脑
: 是IPAD，所以我不认为是在工作，手指频率来看，估计是打游戏
: 全场唯一一个中国孩子，我还是多关注的
: 戴眼镜，个子不高，也抢不到什么球，基本就是外围跟着别人跑而已
: 每次看到那孩子往看台上瞄的时候，我就有点心疼
: 打得不好可能更需要父亲的鼓励吧
: 实际上我LD说这个孩子应该考虑退出
: 父亲不上心篮球，打球的时候又被打击自信心

j*y2014-02-15 08:02

97 楼

那比如 4 3 2 1. 第一个 i + 1 在 i的前面的 i = 3, 4 在 3 前面, 这个就好像不
对了阿。

【在 l*******b 的大作中提到】

: 貌似是这样，从1开始看第一个i+1 在i 的前面就需要n - i步。大家看对不对
: 3124 : 1672345 : 1263745 : 14325

I*e2014-02-15 08:02

98 楼

为啥退出啊？打篮球只是冬天可以进行的一种运动21，有个地方，有些小伙伴一起跑跑
跳跳，就够了。

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

: 主要是形成了一个鲜明的对比，乌泱泱坐满了家长，只有他一个人低头玩电脑
: 是IPAD，所以我不认为是在工作，手指频率来看，估计是打游戏
: 全场唯一一个中国孩子，我还是多关注的
: 戴眼镜，个子不高，也抢不到什么球，基本就是外围跟着别人跑而已
: 每次看到那孩子往看台上瞄的时候，我就有点心疼
: 打得不好可能更需要父亲的鼓励吧
: 实际上我LD说这个孩子应该考虑退出
: 父亲不上心篮球，打球的时候又被打击自信心

p*22014-02-15 08:02

99 楼

要找最小的。找到4,3还要继续往下找。

【在 j*****y 的大作中提到】

: 那比如 4 3 2 1. 第一个 i + 1 在 i的前面的 i = 3, 4 在 3 前面, 这个就好像不
: 对了阿。

w*b2014-02-15 08:02

100 楼

这孩子越打越窝囊，自信全没了

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

: 为啥退出啊？打篮球只是冬天可以进行的一种运动21，有个地方，有些小伙伴一起跑跑
: 跳跳，就够了。

c*t2014-02-15 08:02

101 楼

scala确实很酷，感觉以后会一统江湖

【在 l*******b 的大作中提到】

: def swapEndSort(a: List[Int]) = {
: val b = a.zipWithIndex.sortWith(_._1 < _._1).zipWithIndex
: val i = b.sliding(2).find(x => x(0)._1._2 > x(1)._1._2)
: if(i.isEmpty) 0
: else a.length - i.get(0)._2 - 1
: }
: scala里有些操作list的方法挺好用的，比c++里面强大许多，值得一学

A*u2014-02-15 08:02

102 楼

也许此父亲正在用ipad工作。。。养孩子没有钱的痛苦有多么会妈妈理想呢？

l*b2014-02-15 08:02

103 楼

一统江湖估计不行，实用的functional programming总觉得值得学一下，好多概念不太
一样
haskell 总觉得离能用得上比较远，有个xmonad窗口管理器，很有意思。Scala 的包装
和c之类的还挺接近的，可能好学点

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

: scala确实很酷，感觉以后会一统江湖

I*e2014-02-15 08:02

104 楼

怎么可能，小孩子们都知道：everybody's different
这小孩篮球打得不好不见得他其他方面也都不好
奥本海默体育还差呢，也没见他没自信

【在 w*b 的大作中提到】

: 这孩子越打越窝囊，自信全没了

f*t2014-02-15 08:02

105 楼

O(N)解思路是：
（首先假定数组是1~n的某个排列，如果是随便取一堆不重复的数字排序后也可以做，
复杂度会升至O(NlogN)，空间额外消耗O(N)）
以3, 1, 2, 4为例，首先要找的是最小的数字，也就是1，在它前面的数字全部需要移
到后面。所以1的index是几，就要移动几次。
找到1以后再找2，如果2刚好在1的后面，那么我们不用移它，否则1与2之间有几个数，
我们就要移几次。
依此类推，扫描一遍数组即能得出答案。
public int minSwap(int[] array) {
if (array == null || array.length < 2)
return 0;

int minSwap = 0;
int target = 1, index = 0;
while (index < array.length) {
if (array[index] == target) {
index++;
target++;
} else {
minSwap++;
index++;
}
}

return minSwap;
}

w*b2014-02-15 08:02

106 楼

你是女人你不懂，男孩要是体育不行，在学校里很容易受欺负，慢慢就变得懦弱胆小，
将来去社会也会很ws。世界上有几个奥本海默，大部分都是普通人。

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

: 怎么可能，小孩子们都知道：everybody's different
: 这小孩篮球打得不好不见得他其他方面也都不好
: 奥本海默体育还差呢，也没见他没自信

w*o2014-02-15 08:02

107 楼

luckynoob的算法是对的。
具体实现可以这样：
1。对原数组排序，不过排序结果是index而不是value，比如：[4，3，2，1]排序后得
到[3，2，1，0]，[2，3，7，4]排序后得到[0，1，3，2]
2。对index数组找到第一个降序元素的index i，比如[3，2，1，0]是1，[0，1，3，2]
是3
3。返回n-i

w*t2014-02-15 08:02

108 楼

他们家那不是很小的娃娃了。
想拍球可以自己找地方，找朋友拍
打篮球game，这种竞争是非常直接的，你拿的到球，还是拿不到球
被人挡开了，投进了球没有？
这种结果是非常直接的
打完一场球别人都在讨论，而你连球都没摸到几下
我觉得对自信心确实会有些影响
其实迟早是要放弃篮球的
我一个朋友他孩子本来篮球打的挺不错
后来到了高年级一看黑人打球
就马上退出球队了，说亚裔基本没得打

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

: 为啥退出啊？打篮球只是冬天可以进行的一种运动21，有个地方，有些小伙伴一起跑跑
: 跳跳，就够了。

l*b2014-02-15 08:02

109 楼

nice one!

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

: O(N)解思路是：
: （首先假定数组是1~n的某个排列，如果是随便取一堆不重复的数字排序后也可以做，
: 复杂度会升至O(NlogN)，空间额外消耗O(N)）
: 以3, 1, 2, 4为例，首先要找的是最小的数字，也就是1，在它前面的数字全部需要移
: 到后面。所以1的index是几，就要移动几次。
: 找到1以后再找2，如果2刚好在1的后面，那么我们不用移它，否则1与2之间有几个数，
: 我们就要移几次。
: 依此类推，扫描一遍数组即能得出答案。
: public int minSwap(int[] array) {
: if (array == null || array.length < 2)

l*r2014-02-15 08:02

110 楼

我觉得你们想太多了

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

: 主要是形成了一个鲜明的对比，乌泱泱坐满了家长，只有他一个人低头玩电脑
: 是IPAD，所以我不认为是在工作，手指频率来看，估计是打游戏
: 全场唯一一个中国孩子，我还是多关注的
: 戴眼镜，个子不高，也抢不到什么球，基本就是外围跟着别人跑而已
: 每次看到那孩子往看台上瞄的时候，我就有点心疼
: 打得不好可能更需要父亲的鼓励吧
: 实际上我LD说这个孩子应该考虑退出
: 父亲不上心篮球，打球的时候又被打击自信心

b*e2014-02-15 08:02

111 楼

如果是随便取一堆不重复的数字排序后也可以?
what do you mean """排序后""""也可以做

l*a2014-02-15 08:02

112 楼

我觉得你娃还小，你还没带过娃参加过竞技比赛，其实娃打的好不好和有没有人加油一
毛钱关系都没有。。。可能这个娃本来就打得不好，所以爸爸干脆就不看了，说不定这
老爸就是为了推娃体育才坚持让娃参加的。

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

: 主要是形成了一个鲜明的对比，乌泱泱坐满了家长，只有他一个人低头玩电脑
: 是IPAD，所以我不认为是在工作，手指频率来看，估计是打游戏
: 全场唯一一个中国孩子，我还是多关注的
: 戴眼镜，个子不高，也抢不到什么球，基本就是外围跟着别人跑而已
: 每次看到那孩子往看台上瞄的时候，我就有点心疼
: 打得不好可能更需要父亲的鼓励吧
: 实际上我LD说这个孩子应该考虑退出
: 父亲不上心篮球，打球的时候又被打击自信心

y*n2014-02-15 08:02

113 楼

你的思路是对的，算法是有问题的。
比如：1, 2, 1, 2
只需swap一次，你的算法返回2。
我找到的方法和你的几乎一样，只是需要扫描两遍。

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

: O(N)解思路是：
: （首先假定数组是1~n的某个排列，如果是随便取一堆不重复的数字排序后也可以做，
: 复杂度会升至O(NlogN)，空间额外消耗O(N)）
: 以3, 1, 2, 4为例，首先要找的是最小的数字，也就是1，在它前面的数字全部需要移
: 到后面。所以1的index是几，就要移动几次。
: 找到1以后再找2，如果2刚好在1的后面，那么我们不用移它，否则1与2之间有几个数，
: 我们就要移几次。
: 依此类推，扫描一遍数组即能得出答案。
: public int minSwap(int[] array) {
: if (array == null || array.length < 2)

l*r2014-02-15 08:02

114 楼

小孩的game本来就是玩个热闹，你说的这个估计也肯定是recreational组的，没有那么
serious.
不同家长参加这种业余组的目的不一样，有的是为了以后去高级组打基础的，也有些完
全打酱油的，只是为了让娃去跑跑跳跳，碰不碰到球人也许根本无所谓。
AAU俱乐部会serious很多，在哪儿估计你不会看到这个爸爸这样的家长。

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

: 他们家那不是很小的娃娃了。
: 想拍球可以自己找地方，找朋友拍
: 打篮球game，这种竞争是非常直接的，你拿的到球，还是拿不到球
: 被人挡开了，投进了球没有？
: 这种结果是非常直接的
: 打完一场球别人都在讨论，而你连球都没摸到几下
: 我觉得对自信心确实会有些影响
: 其实迟早是要放弃篮球的
: 我一个朋友他孩子本来篮球打的挺不错
: 后来到了高年级一看黑人打球

y*n2014-02-15 08:02

115 楼

这道题如果数组内容是杂乱的有重复依然可以O(N)搞定。

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

: O(N)解思路是：
: （首先假定数组是1~n的某个排列，如果是随便取一堆不重复的数字排序后也可以做，
: 复杂度会升至O(NlogN)，空间额外消耗O(N)）
: 以3, 1, 2, 4为例，首先要找的是最小的数字，也就是1，在它前面的数字全部需要移
: 到后面。所以1的index是几，就要移动几次。
: 找到1以后再找2，如果2刚好在1的后面，那么我们不用移它，否则1与2之间有几个数，
: 我们就要移几次。
: 依此类推，扫描一遍数组即能得出答案。
: public int minSwap(int[] array) {
: if (array == null || array.length < 2)

b*i2014-02-15 08:02

116 楼

这么说吧，一个好的父亲，在那种场合，是应该对场上自己的儿子关注的，哪怕现实是
他是自己孩子唯一的一观众和粉丝。这就叫上阵父子兵。
退一步说，就是装，也得装出来，哪怕趁儿子不注意的时候再低头吐，或者完后回家路
上跟儿子说你打得太烂了要不咱退了？
这个不是做人的素质，是做爹的素质。公开场合只要需要，老子就绝对拿枪，哦不，拿
肩膀顶在儿子背后。
我没孩子的时候，大学里有个朋友是美国孩子，我见过他爹，他看着他儿子的那种欣赏
和慈爱的眼神，我这么多年了都记得很清晰。
前两天看一个冬奥会的广告，内容刚好类似你说的这种比赛场景。
但是，那个会做烤鸭的大妈说得好，自家孩子自家疼。
爱谁谁。

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

: 他们家那不是很小的娃娃了。
: 想拍球可以自己找地方，找朋友拍
: 打篮球game，这种竞争是非常直接的，你拿的到球，还是拿不到球
: 被人挡开了，投进了球没有？
: 这种结果是非常直接的
: 打完一场球别人都在讨论，而你连球都没摸到几下
: 我觉得对自信心确实会有些影响
: 其实迟早是要放弃篮球的
: 我一个朋友他孩子本来篮球打的挺不错
: 后来到了高年级一看黑人打球

y*n2014-02-15 08:02

117 楼

思路：
1. 逆序遍历，凡是比后面最小值min大的元素，都需要swap。
并且记录其中最小值swapMin。
2. 再次逆序遍历，把第一次没数过的并且比swapMin大的都需要swap。
假设输入参数不为空：
public static int MinSwap(int[] arr)
{
int swapCount = 0;
int swapMin = int.MaxValue;
int min = int.MaxValue;
for (int i = arr.Length - 1; i >= 0; i--)
if (arr[i] > min)
{
swapCount++;
if (arr[i] < swapMin)
swapMin = arr[i];
}
else if (arr[i] < min)
min = arr[i];
min = int.MaxValue;
for (int i = arr.Length - 1; i >= 0; i--)
{
if ((arr[i] <= min) && (arr[i] > swapMin))
swapCount++;
if (arr[i] < min)
min = arr[i];
}
return swapCount;
}

r*i2014-02-15 08:02

118 楼

哎哟大叔您这话说得，那丝贼对咧。

【在 b********i 的大作中提到】

: 这么说吧，一个好的父亲，在那种场合，是应该对场上自己的儿子关注的，哪怕现实是
: 他是自己孩子唯一的一观众和粉丝。这就叫上阵父子兵。
: 退一步说，就是装，也得装出来，哪怕趁儿子不注意的时候再低头吐，或者完后回家路
: 上跟儿子说你打得太烂了要不咱退了？
: 这个不是做人的素质，是做爹的素质。公开场合只要需要，老子就绝对拿枪，哦不，拿
: 肩膀顶在儿子背后。
: 我没孩子的时候，大学里有个朋友是美国孩子，我见过他爹，他看着他儿子的那种欣赏
: 和慈爱的眼神，我这么多年了都记得很清晰。
: 前两天看一个冬奥会的广告，内容刚好类似你说的这种比赛场景。
: 但是，那个会做烤鸭的大妈说得好，自家孩子自家疼。

s*t2014-02-15 08:02

119 楼

那比如 3762514
第一个降序元素的index是5，返回7-5=2
总共换2次就行啦？怎么换啊

2]

【在 w***o 的大作中提到】

: luckynoob的算法是对的。
: 具体实现可以这样：
: 1。对原数组排序，不过排序结果是index而不是value，比如：[4，3，2，1]排序后得
: 到[3，2，1，0]，[2，3，7，4]排序后得到[0，1，3，2]
: 2。对index数组找到第一个降序元素的index i，比如[3，2，1，0]是1，[0，1，3，2]
: 是3
: 3。返回n-i

N*n2014-02-15 08:02

120 楼

真是个好爸爸。

【在 b********i 的大作中提到】

: 这么说吧，一个好的父亲，在那种场合，是应该对场上自己的儿子关注的，哪怕现实是
: 他是自己孩子唯一的一观众和粉丝。这就叫上阵父子兵。
: 退一步说，就是装，也得装出来，哪怕趁儿子不注意的时候再低头吐，或者完后回家路
: 上跟儿子说你打得太烂了要不咱退了？
: 这个不是做人的素质，是做爹的素质。公开场合只要需要，老子就绝对拿枪，哦不，拿
: 肩膀顶在儿子背后。
: 我没孩子的时候，大学里有个朋友是美国孩子，我见过他爹，他看着他儿子的那种欣赏
: 和慈爱的眼神，我这么多年了都记得很清晰。
: 前两天看一个冬奥会的广告，内容刚好类似你说的这种比赛场景。
: 但是，那个会做烤鸭的大妈说得好，自家孩子自家疼。

M*e2014-02-15 08:02

121 楼

完了，俺娃周末踢球的一小时，俺赶快托付另一个妈妈帮看着，自己跑出去run
errands勒。。。。深刻反省中。。。

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

: 每周六带儿子去游泳课，GYM里同时间有2场篮球GAME
: 儿子游完泳我通常会带他看第一场的下半场，和第二场的上半场
: 每一场GAME有16个男孩，2场就是32个男孩
: 所有家长都坐在观众席给孩子们呐喊加油，鼓掌，还有拍照，相互聊天。。。
: 我这个局外人也不例外
: 32个孩子里只有一个中国孩子，每次都是爸爸带过来
: 每一个星期，每一场，这个爸爸都从头到尾低着头玩 IPAD
: 真不夸张，从来没有见他抬头看一眼儿子
: 其它的父母没有一个玩手机或者IPAD或任何电子产品
: 其实作为妈妈，我对体育活动根本没什么兴趣

l*a2014-02-15 08:02

122 楼

做爹的都有这觉悟就好了。。。

【在 b********i 的大作中提到】

: 这么说吧，一个好的父亲，在那种场合，是应该对场上自己的儿子关注的，哪怕现实是
: 他是自己孩子唯一的一观众和粉丝。这就叫上阵父子兵。
: 退一步说，就是装，也得装出来，哪怕趁儿子不注意的时候再低头吐，或者完后回家路
: 上跟儿子说你打得太烂了要不咱退了？
: 这个不是做人的素质，是做爹的素质。公开场合只要需要，老子就绝对拿枪，哦不，拿
: 肩膀顶在儿子背后。
: 我没孩子的时候，大学里有个朋友是美国孩子，我见过他爹，他看着他儿子的那种欣赏
: 和慈爱的眼神，我这么多年了都记得很清晰。
: 前两天看一个冬奥会的广告，内容刚好类似你说的这种比赛场景。
: 但是，那个会做烤鸭的大妈说得好，自家孩子自家疼。

h*e2014-02-15 08:02

123 楼

那你们就坐过去吧，问问哪个孩子是你的(虽然是废话一句)，然后帮着加加油，也许爸
爸就不好意思了意识到自己的问题也跟着加油了。
我家这个篮球训练的时候我也看的，倒不是多关心他打球进步，主要是不看着臭小子就
fool around，得盯着，汗。。。

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

: 主要是形成了一个鲜明的对比，乌泱泱坐满了家长，只有他一个人低头玩电脑
: 是IPAD，所以我不认为是在工作，手指频率来看，估计是打游戏
: 全场唯一一个中国孩子，我还是多关注的
: 戴眼镜，个子不高，也抢不到什么球，基本就是外围跟着别人跑而已
: 每次看到那孩子往看台上瞄的时候，我就有点心疼
: 打得不好可能更需要父亲的鼓励吧
: 实际上我LD说这个孩子应该考虑退出
: 父亲不上心篮球，打球的时候又被打击自信心

a*t2014-02-15 08:02

124 楼

觉悟不错哈。

【在 b********i 的大作中提到】

: 这么说吧，一个好的父亲，在那种场合，是应该对场上自己的儿子关注的，哪怕现实是
: 他是自己孩子唯一的一观众和粉丝。这就叫上阵父子兵。
: 退一步说，就是装，也得装出来，哪怕趁儿子不注意的时候再低头吐，或者完后回家路
: 上跟儿子说你打得太烂了要不咱退了？
: 这个不是做人的素质，是做爹的素质。公开场合只要需要，老子就绝对拿枪，哦不，拿
: 肩膀顶在儿子背后。
: 我没孩子的时候，大学里有个朋友是美国孩子，我见过他爹，他看着他儿子的那种欣赏
: 和慈爱的眼神，我这么多年了都记得很清晰。
: 前两天看一个冬奥会的广告，内容刚好类似你说的这种比赛场景。
: 但是，那个会做烤鸭的大妈说得好，自家孩子自家疼。

g*o2014-02-15 08:02

125 楼

你也别愁了，可能这个家庭的教育方式就是这样的，比较放手，不是以娃为中心？
其实我有时候也好奇，是不是这样子娃会更独立，更酷一点。
我家和你家一样，围着娃为中心转的，有时候觉得是不是也不太好？世界不是围着娃转
的呀，需要挫折教育～～

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

: 主要是形成了一个鲜明的对比，乌泱泱坐满了家长，只有他一个人低头玩电脑
: 是IPAD，所以我不认为是在工作，手指频率来看，估计是打游戏
: 全场唯一一个中国孩子，我还是多关注的
: 戴眼镜，个子不高，也抢不到什么球，基本就是外围跟着别人跑而已
: 每次看到那孩子往看台上瞄的时候，我就有点心疼
: 打得不好可能更需要父亲的鼓励吧
: 实际上我LD说这个孩子应该考虑退出
: 父亲不上心篮球，打球的时候又被打击自信心

w*t2014-02-15 08:02

126 楼

我不会再多说什么了。我们家肯定不是以娃为中心的。

【在 g*****o 的大作中提到】

: 你也别愁了，可能这个家庭的教育方式就是这样的，比较放手，不是以娃为中心？
: 其实我有时候也好奇，是不是这样子娃会更独立，更酷一点。
: 我家和你家一样，围着娃为中心转的，有时候觉得是不是也不太好？世界不是围着娃转
: 的呀，需要挫折教育～～

g*o2014-02-15 08:02

127 楼

完了，那我得好好反省自己了，总是围着娃为中心

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

: 我不会再多说什么了。我们家肯定不是以娃为中心的。