[spoiler]The man in the high castle高堡奇人 - 未名空间MITBBS历史存档

[spoiler]The man in the high castle高堡奇人# Movie - 无限影话

K*g2016-12-27 08:12

1 楼

find out all the elements in a sorted integer array whose value is equal to
index of the array. O(logn) solution is expected.
请不要随便说个binary search，那样等于没有说。请教一个很详细的步骤，并且有例
子。多谢！

c*i2016-12-27 08:12

2 楼

用圣诞节四天把两季全都看完了，每个结尾都是一个小高潮。
每一集的编剧都不同，整个故事仍然极其有连贯性。
剧情开始于二战的一个alternative reality，德国和日本赢得了战争，
因为德国先发展出了原子弹，并且成功刺杀了美国总统罗斯福。
在1947年战争结束之后，德国和日本把美国分成了……三块：
西边2/3地盘以纽约为经济政治中心的是德国殖民地，
东边加州等以三番为中心的是日本殖民地，
中间有一个lawless的neutral zone不归谁管。
世界也大致被德/日所分裂统治着，德国奉行Aryan白人血统至上甚至对
非洲进行了种族灭绝。
由于德国的科技超出了日本[日本没有原子弹]，所以战后的和平是一种虚伪的假象。
1962年，德国的元首希特勒 - 这是我在所有战争片中看到描写的最正面的元首形象 -
已经在疾病和战争后，垂垂老矣即将就木，却很意外地不希望挑起对日本的战争。
同时，德军中的主战阴谋派蠢蠢欲动，挑起一个又一个阴谋，试图在希特勒生病死亡
权力交接的时候掌握权力并且发动对日本及其殖民地的核打击。
日本处于军事弱势的一方，只好咽下皇太子差点被暗杀的耻辱，见招坼招。
同时，由于地下党resistance美国民众自发的反抗，
德日在美国本土的统治也受到冲击。
组织地下党的理想主义者 - 一个自称The man in the high castle的人，
他出于某种未知的原因，可以把一个travel to future的那些人的经历，
以film的方式带回到现在这个世界。
而现在这个世界的人看到了那些alternative reality history，
可以对现有的策略作出相应的修改，从而gain the upper hand。
所有的势力都在发了疯一样的搜集这些film。
几点感想：
1. 中间几个线索比如圣经KJV某章节12:5中的grasshopper没有发展下去。
2. 人物的道德非常灰色，观众很容易去同情理解那些原本是反面的人物。
3. 主角三人Juliana/Frank/Joe演技较差；
副角比如John Smith/Tagomi/Kido演技精湛，非常有立体感。
4. 好奇心杀死猫。
其实观众和Juliana一样，是为了知道这些film到底是干什么的孤身冒险。
可是，这些东西真的值得付出性命吗？ No?
Resistance真的占据了道德上的至高感吗？也许未必。
5. 东方的冥想和易经，似乎是可以travel to the alternative world的一种途径。
到了第二季，Tagomi的重要任务就是梦游太虚并且拿回一个film去威慑对方。
6. Nazi的拷问骗人技巧出神入化，比如Smith如何去忽悠Heydrich说出阴谋派的幕后
boss。
还有Smith对于Joe, Juliana的感情投资，拿捏的都很到位。
相比起Smith对Joe而言，Tagomi对Juliana则更加真诚。
7. 低层的小人物总是被上面的人忽悠，到了desperado的时候去革命反抗，
然后总觉得自己可以change something - 其实很多时候是一厢情愿的幻想。
其实上位者的决策一般都是正确的，盖因他们有更加全面立体的信息而已。
在season 1 episode 10 - a way out里面的结局就是这个意思。
8. 同理，如果小人物能够掌握多方位的关键信息，并且logically connect the dot，
也可以变成翻云覆雨之人。比如Juliana一直就和film有关系，
所以一直能够do some real change。

o*i2016-12-27 08:12

3 楼

既然已经sorted了，难道不是O(n)就可以了？扫描一遍就ok了呀

to

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

: find out all the elements in a sorted integer array whose value is equal to
: index of the array. O(logn) solution is expected.
: 请不要随便说个binary search，那样等于没有说。请教一个很详细的步骤，并且有例
: 子。多谢！

a*32016-12-27 08:12

4 楼

严重剧透都没说明吗？！

c*e2016-12-27 08:12

5 楼

how could O(logn) be possible if the array looks like below:
[0, 1, 2, 3, 4, 5, 6, 7, ..., ]
that is, each element's value = its own index
in the worst case, you have to scan all the elements. O(n)

to

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

: find out all the elements in a sorted integer array whose value is equal to
: index of the array. O(logn) solution is expected.
: 请不要随便说个binary search，那样等于没有说。请教一个很详细的步骤，并且有例
: 子。多谢！

c*i2016-12-27 08:12

6 楼

标题spoiler!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

i*e2016-12-27 08:12

7 楼

agree

how could O(logn) be possible if the array looks like below:
[0, 1, 2, 3, 4, 5, 6, 7, ..., ]
that is, each element's value = its own index
in the worst case, you have to scan all the elements. O(n)
to

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

: how could O(logn) be possible if the array looks like below:
: [0, 1, 2, 3, 4, 5, 6, 7, ..., ]
: that is, each element's value = its own index
: in the worst case, you have to scan all the elements. O(n)
:
: to

l*z2016-12-27 08:12

8 楼

女主角长的如何没说

g*n2016-12-27 08:12

9 楼

在所有元素都unique的情况下，可以用log(n)时间找出所有value = index的元素的
range，因为
这样的range只能有一个，这样这个题就变成了用log(n)时间找出最小的和最大的value
= index的
元素（range边界）了。
假设排序是递增的，用2步分别找最小和最大元素。
1. 找最小：用b-search的方法，找到mid-index后，比较value是否大于index。如果大
于，则目标
在左half。如果小于，则目标在右。如果等于，目标还是在左。
2. 找最大：把等于的情况，改成目标在右。

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

: how could O(logn) be possible if the array looks like below:
: [0, 1, 2, 3, 4, 5, 6, 7, ..., ]
: that is, each element's value = its own index
: in the worst case, you have to scan all the elements. O(n)
:
: to

r*x2016-12-27 08:12

10 楼

这剧透的怎么看

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

: 用圣诞节四天把两季全都看完了，每个结尾都是一个小高潮。
: 每一集的编剧都不同，整个故事仍然极其有连贯性。
: 剧情开始于二战的一个alternative reality，德国和日本赢得了战争，
: 因为德国先发展出了原子弹，并且成功刺杀了美国总统罗斯福。
: 在1947年战争结束之后，德国和日本把美国分成了……三块：
: 西边2/3地盘以纽约为经济政治中心的是德国殖民地，
: 东边加州等以三番为中心的是日本殖民地，
: 中间有一个lawless的neutral zone不归谁管。
: 世界也大致被德/日所分裂统治着，德国奉行Aryan白人血统至上甚至对
: 非洲进行了种族灭绝。

f*52016-12-27 08:12

11 楼

why?
for example.sizeof(a)=8
lo=0,hi=8 //lo mean start index of binary search
// hi means end index of binary search
mid=(lo+hi)/2;
when u found that a[mid]=mid
u don't need to check a[0]..a[mid-1]...
then u can use binary search...
make sense?

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

: how could O(logn) be possible if the array looks like below:
: [0, 1, 2, 3, 4, 5, 6, 7, ..., ]
: that is, each element's value = its own index
: in the worst case, you have to scan all the elements. O(n)
:
: to

A*o2016-12-27 08:12

12 楼

没透啥，主要说的是背景。。。我觉得这片子主要是作家的想法NB，但是情节/故事
满弱的，架空世界么，虫子狠多地。。。现实世界捉虫容易一些，可以理解。
总体还算不错，没啥科幻，当作历史剧看也可以。。。

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

: 这剧透的怎么看

g*n2016-12-27 08:12

13 楼

所有value=index的数在一个并且只在一个range中，是个隐含的性质。找到了这个性质
，就可以很容
易想到找range的边界了，复杂度仍然是log(n)。当然，如果要打印出这些数，那么复
杂度就是(n)了。

equal to

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

: find out all the elements in a sorted integer array whose value is equal to
: index of the array. O(logn) solution is expected.
: 请不要随便说个binary search，那样等于没有说。请教一个很详细的步骤，并且有例
: 子。多谢！

r*x2016-12-27 08:12

14 楼

太剧透啦

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

: 用圣诞节四天把两季全都看完了，每个结尾都是一个小高潮。
: 每一集的编剧都不同，整个故事仍然极其有连贯性。
: 剧情开始于二战的一个alternative reality，德国和日本赢得了战争，
: 因为德国先发展出了原子弹，并且成功刺杀了美国总统罗斯福。
: 在1947年战争结束之后，德国和日本把美国分成了……三块：
: 西边2/3地盘以纽约为经济政治中心的是德国殖民地，
: 东边加州等以三番为中心的是日本殖民地，
: 中间有一个lawless的neutral zone不归谁管。
: 世界也大致被德/日所分裂统治着，德国奉行Aryan白人血统至上甚至对
: 非洲进行了种族灭绝。

g*n2016-12-27 08:12

15 楼

很不make sense。按你说的，如果lo=0,hi=8并且n=8，因为数列是有序的，那根本不用
任何check整
个数列就是解。
如果不是这种情况，你的方法我不知道是什么意思。

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

: why?
: for example.sizeof(a)=8
: lo=0,hi=8 //lo mean start index of binary search
: // hi means end index of binary search
: mid=(lo+hi)/2;
: when u found that a[mid]=mid
: u don't need to check a[0]..a[mid-1]...
: then u can use binary search...
: make sense?

c*i2016-12-27 08:12

16 楼

女主角长得不错，不过不是我的菜。
最后一集女主角有Mary Sue之嫌。
不过这部剧不是为了看主角的，是为了看那些可以有Time travel的高堡奇人（们）的
。

i*e2016-12-27 08:12

17 楼

Thanks 理解你的意思了也就是说原题实际就是在用b-search找两个边界

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

: 所有value=index的数在一个并且只在一个range中，是个隐含的性质。找到了这个性质
: ，就可以很容
: 易想到找range的边界了，复杂度仍然是log(n)。当然，如果要打印出这些数，那么复
: 杂度就是(n)了。
:
: equal to

c*i2016-12-27 08:12

18 楼

Time travel满地是虫……
不过据说人要在A世界挂了或者不存在，B世界的人才能穿过去，
这样就不会有在平行世界碰到自己的尴尬了。
比如Tagomi在our reality后来跳桥自杀之后，
在Nazi win那个世界才能穿越过去。

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

: 没透啥，主要说的是背景。。。我觉得这片子主要是作家的想法NB，但是情节/故事
: 满弱的，架空世界么，虫子狠多地。。。现实世界捉虫容易一些，可以理解。
: 总体还算不错，没啥科幻，当作历史剧看也可以。。。

g*n2016-12-27 08:12

19 楼

我认为是这样的，这是这题的一个隐含性质。

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

: Thanks 理解你的意思了也就是说原题实际就是在用b-search找两个边界

z*n2016-12-27 08:12

20 楼

制作低廉，水平不够精良
70分水平的剧
这年头太多90分级别的了，这个一对比就显得差了不少

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

: 女主角长得不错，不过不是我的菜。
: 最后一集女主角有Mary Sue之嫌。
: 不过这部剧不是为了看主角的，是为了看那些可以有Time travel的高堡奇人（们）的
: 。

Z*Z2016-12-27 08:12

21 楼

这个方法可以扩展到在sorted数组里面找一个给定元素吧，数组允许重复。也是找2次，
一次下界一次上界

value

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

: 在所有元素都unique的情况下，可以用log(n)时间找出所有value = index的元素的
: range，因为
: 这样的range只能有一个，这样这个题就变成了用log(n)时间找出最小的和最大的value
: = index的
: 元素（range边界）了。
: 假设排序是递增的，用2步分别找最小和最大元素。
: 1. 找最小：用b-search的方法，找到mid-index后，比较value是否大于index。如果大
: 于，则目标
: 在左half。如果小于，则目标在右。如果等于，目标还是在左。
: 2. 找最大：把等于的情况，改成目标在右。

c*i2016-12-27 08:12

22 楼

一个好剧本比十个特效都牛
这个剧，不是智力超常的人看不了
不过日军那里的制作是太粗糙了，就给人看一些cubical -_-
还是纳粹那边的养眼，制服和剧情都棒

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

: 制作低廉，水平不够精良
: 70分水平的剧
: 这年头太多90分级别的了，这个一对比就显得差了不少

f*52016-12-27 08:12

23 楼

如果a[mid]!=mid,then u only need to check a[0]..a[mid-1]
u can ignore a[mid+1]..a[n]
since it is impossible that a[mid]简单说，这道题就是binary search找一个位置。
你找到第一个不是a[index]==index的以后，后面的都不拢考虑了
前面的就是结果

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

: 很不make sense。按你说的，如果lo=0,hi=8并且n=8，因为数列是有序的，那根本不用
: 任何check整
: 个数列就是解。
: 如果不是这种情况，你的方法我不知道是什么意思。

j*n2016-12-27 08:12

24 楼

女主颜值太低。。。

g*n2016-12-27 08:12

25 楼

"since it is impossible that a[mid]负数。这就是为什么我说那个range有两个边界。

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

: 如果a[mid]!=mid,then u only need to check a[0]..a[mid-1]
: u can ignore a[mid+1]..a[n]
: since it is impossible that a[mid]: 简单说，这道题就是binary search找一个位置。
: 你找到第一个不是a[index]==index的以后，后面的都不拢考虑了
: 前面的就是结果

k*a2016-12-27 08:12

26 楼

女主身材很好

f*52016-12-27 08:12

27 楼

en
这点我忽视了。
看题不仔细啊。。

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

: "since it is impossible that a[mid]: 负数。这就是为什么我说那个range有两个边界。

A*o2016-12-27 08:12

28 楼

我还真不指这样的虫。。。俺们世界的部分逻辑，尤其因果关系，是建立在
时间先后的顺序上的，时间穿越逻辑上必然有问题，这个属于内生缺陷，可
以象你那样杀，也可以不杀。。。反正杀不干净。。。
我主要觉得作家Handle不了宏大历史场面，场面一大了狠多情节比较儿戏。。。

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

: Time travel满地是虫……
: 不过据说人要在A世界挂了或者不存在，B世界的人才能穿过去，
: 这样就不会有在平行世界碰到自己的尴尬了。
: 比如Tagomi在our reality后来跳桥自杀之后，
: 在Nazi win那个世界才能穿越过去。

g*n2016-12-27 08:12

29 楼

恩，有道理

次，

【在 Z*****Z 的大作中提到】

: 这个方法可以扩展到在sorted数组里面找一个给定元素吧，数组允许重复。也是找2次，
: 一次下界一次上界
:
: value

r*x2016-12-27 08:12

30 楼

太剧透啦

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

: 用圣诞节四天把两季全都看完了，每个结尾都是一个小高潮。
: 每一集的编剧都不同，整个故事仍然极其有连贯性。
: 剧情开始于二战的一个alternative reality，德国和日本赢得了战争，
: 因为德国先发展出了原子弹，并且成功刺杀了美国总统罗斯福。
: 在1947年战争结束之后，德国和日本把美国分成了……三块：
: 西边2/3地盘以纽约为经济政治中心的是德国殖民地，
: 东边加州等以三番为中心的是日本殖民地，
: 中间有一个lawless的neutral zone不归谁管。
: 世界也大致被德/日所分裂统治着，德国奉行Aryan白人血统至上甚至对
: 非洲进行了种族灭绝。

j*l2016-12-27 08:12

31 楼

我开始把原题看成你说的这题了。
如果是你这题
第一步，如果有相同元素，找到index最小的那个
第二步，如果有相同元素，找到index最大的那个
Programming Pearls上有讨论怎么做这种变体的方法，思路就是当mid元素等于待查元
素时候让
lower = mid 或 upper = mid, 并且在还剩两个元素的时候就要停止

次，

【在 Z*****Z 的大作中提到】

: 这个方法可以扩展到在sorted数组里面找一个给定元素吧，数组允许重复。也是找2次，
: 一次下界一次上界
:
: value

K*g2016-12-27 08:12

32 楼

不错。好像很对。

value

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

: 在所有元素都unique的情况下，可以用log(n)时间找出所有value = index的元素的
: range，因为
: 这样的range只能有一个，这样这个题就变成了用log(n)时间找出最小的和最大的value
: = index的
: 元素（range边界）了。
: 假设排序是递增的，用2步分别找最小和最大元素。
: 1. 找最小：用b-search的方法，找到mid-index后，比较value是否大于index。如果大
: 于，则目标
: 在左half。如果小于，则目标在右。如果等于，目标还是在左。
: 2. 找最大：把等于的情况，改成目标在右。

s*l2016-12-27 08:12

33 楼

这题如果有重复元素的话只能o(n)吧？

f*52016-12-27 08:12

34 楼

不对
如果是 a[index]==index && a[index +/- 1]=index
就不满足题意了，

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

: 这题如果有重复元素的话只能o(n)吧？

s*l2016-12-27 08:12

35 楼

题目没说 array都是unique value啊~
可以这样子吧~
1 1 1 2 5 6 7...

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

: 不对
: 如果是 a[index]==index && a[index +/- 1]=index
: 就不满足题意了，

h*62016-12-27 08:12

36 楼

如果所有元素都不同，可以把所有元素减去其下标，可以证明新数组仍然是有序的
，这时用二分法找出值为0的元素的起止位置。
第一步减下标复杂度为O(n)，但是可以不实际减，仅仅在脑海中想象减，这样直接进
行第二步，复杂度为O(log n)。
如果没有所有元素不同的条件，还是老老实实一个一个比较吧，复杂度O(n)。