BSO 一下百元HTPC - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Hardware - 计算机硬件

BSO 一下百元HTPC

BSO 一下百元HTPC# Hardware - 计算机硬件

a*82013-01-11 08:01

1 楼

1. First greater number in an array. Given a large array of positive
integers, for an arbitrary integer A, we want to know the first integer in
the array which is greater than or equal A . O(logn) solution required
ex [2, 10,5,6,80]
input : 6 output : 10
input :20 output : 80
没想到Lg(n)的办法
2. 一堆数，其中一些数出现了一次，一些数出现了两次，只有一个数出现了三次
找出那个出现了3次的数, hash方法很trivial 就不说了
没想到不用hahs怎么做。

w*22013-01-11 08:01

2 楼

节前打算百元左右搞个HTPC，CPU定位在Llano。
但搞到了新蛋的免费主板，CPU就不满足于Llano了。
本来电源和机箱都是用的旧的。最近赶上micro center 25 off，被逼更新。
下面是配置清单，感觉做HTPC有点屈了。
CPU MC FX4100 95.4-10-26
Motherboard Newegg Asus M5A97 LE 25-25
Video Newegg Gigabyte 6450 36.99-25
RAM Tigerdirect Kingston HyperX Red 2X4G 35-15
MC Thermaltake V3 Case 11.6-10
MC Inland 500w Golden PSU 5.30
HDD old 150G
USB 1 G with openelec
共85刀rebate，全部拿到的话，成本99刀。

s*g2013-01-11 08:01

3 楼

我相信第一题是不可能用lgn做出来的。一个简单的反例就是，如果没有比A大的数，怎么办，如果不是sorted，怎么的你也得O（n）去发现这个事实，这是谁出的面试题？

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

: 1. First greater number in an array. Given a large array of positive
: integers, for an arbitrary integer A, we want to know the first integer in
: the array which is greater than or equal A . O(logn) solution required
: ex [2, 10,5,6,80]
: input : 6 output : 10
: input :20 output : 80
: 没想到Lg(n)的办法
: 2. 一堆数，其中一些数出现了一次，一些数出现了两次，只有一个数出现了三次
: 找出那个出现了3次的数, hash方法很trivial 就不说了
: 没想到不用hahs怎么做。

a*82013-01-11 08:01

4 楼

我也邪门，可能没写清楚，我估计这个数组是两个递增序列，这个做lgn是完全可能的

d*i2013-01-11 08:01

5 楼

1, 我的想法:
建立一个pair 序列(value, original position)
(2, 1)
(10, 2)
(5, 3)
(6, 4)
(80, 5)
然后先把这个序列排好序,注意对于这样一个数组,这个排序只要做一次,因此是
constant time的cost
(2, 1)
(5, 3)
(6, 4)
(10, 2)
(80, 5)
再整理一次,找出比每个数大的后面所有序列里,original index最小而且小于该数的original index,中间的original index也可以不保存了,这个也是一次性的cost.
(2, 1, 10)
(5, 3, 10)
(6, 4, 10)
(10, 2, 80)
(80, 5, -1)
以后根据input 二分查找,返回tuple里第三个值.由于数组大,如果查找的次数足够多,
预处理是可以接受的办法.

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

g*e2013-01-11 08:01

6 楼

lgN是指平均complicity，O(N)是最坏情况。这个与Qsort同理。是个经典算法题，类似
qsort的操作就可以了。

怎么办，如果不是sorted，怎么的你也得O（n）去发现这个事实，这是谁出的面试题？

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

: 我相信第一题是不可能用lgn做出来的。一个简单的反例就是，如果没有比A大的数，怎么办，如果不是sorted，怎么的你也得O（n）去发现这个事实，这是谁出的面试题？

j*a2013-01-11 08:01

7 楼

就算是平均complexity也不可能是LogN吧？像qsort run一个iteration也要O(N)啊？
请指教...

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

: lgN是指平均complicity，O(N)是最坏情况。这个与Qsort同理。是个经典算法题，类似
: qsort的操作就可以了。
:
: 怎么办，如果不是sorted，怎么的你也得O（n）去发现这个事实，这是谁出的面试题？

H*X2013-01-11 08:01

8 楼

qsort也是nlogn..

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

p*72013-01-11 08:01

9 楼

第一个题预处理是必须的
先根据大小对数组排序，下面是他们的序号
2 5 6 10 80
然后创建一个hash table key是这些数值，value是这些数first greater number in the
array
然后遍历原数组，并且保持一个stack
遍历的逻辑如下
如果没查到这个数插入
如数比栈顶的大就弹出前面的，并且在table里面找到前面这个数，把后面这个数写入value，然后
继续比较栈顶，知道比栈顶的数小，最后压入栈顶。
如果比栈顶的小就压入
预处理结束后，查找的逻辑是
hash 查输入是不是存在，如果不存在，就binary 查找这个数字，如果这个数存在就能直接获得哪
个数是first greater value
最差复杂度是LogN

integer
in

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

h*62013-01-11 08:01

10 楼

如果可以预处理那就简单了，求出一个优先增长子序列就可以了，如原题，是2, 10,
80。
优先增长子序列是我自己起的名字，方法是把下一个比子序列中最后一个元素更大的元
素加入序列中，遍历原数组所得到的子序列。
于是乎：
第一个大于等于0~2的是2，
第一个大于等于3~10的是10，
第一个大于等于11~80的是80，
第一个大于等于81的没有。

h*k2013-01-11 08:01

11 楼

预处理没有这么复杂，只需要生成一个序列就行，在这个序列里每个元素是一个pair，
第一个值表示在原数组中的index，第二个值是表示在原数组中这个index下的值。注意
，对于所有pair，第二个值是单调递增的。
比如对于例子[2, 10,5,6,80] 来说，生成的序列为
(0，2),(1,10),(4,80)
这个预处理过程需要扫描原数组一遍就可以了。
然后对于给定的值k，在生成的序列中的第二个值进行二差查找，返回第一个比它大的
pair中的index值。比如查找30，返回4。

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

: 1, 我的想法:
: 建立一个pair 序列(value, original position)
: (2, 1)
: (10, 2)
: (5, 3)
: (6, 4)
: (80, 5)
: 然后先把这个序列排好序,注意对于这样一个数组,这个排序只要做一次,因此是
: constant time的cost
: (2, 1)

f*g2013-01-11 08:01

12 楼

Agree. For unsorted array, you need to scan the whole array at least.
Sort the array first, then do binary search. It will take nlogn times

怎么办，如果不是
sorted，怎么的你也得O（n）去发现这个事实，这是谁出的面试题？

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

a*82013-01-11 08:01

13 楼

是正解, 不用全部排序。

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

: 预处理没有这么复杂，只需要生成一个序列就行，在这个序列里每个元素是一个pair，
: 第一个值表示在原数组中的index，第二个值是表示在原数组中这个index下的值。注意
: ，对于所有pair，第二个值是单调递增的。
: 比如对于例子[2, 10,5,6,80] 来说，生成的序列为
: (0，2),(1,10),(4,80)
: 这个预处理过程需要扫描原数组一遍就可以了。
: 然后对于给定的值k，在生成的序列中的第二个值进行二差查找，返回第一个比它大的
: pair中的index值。比如查找30，返回4。

a*82013-01-11 08:01

14 楼

第二道有没有有好的解法？
如果只有一个数出现奇数次，其他出现偶数次，那异或运算可以找出来。
主要麻烦是有一些数出现1次，极端情况是所有其他数都出现1次，一个数出现三次。
2. 一堆数，其中一些数出现了一次，一些数出现了两次，只有一个数出现了三次
找出那个出现了3次的数, hash方法很trivial 就不说了
没想到不用hahs怎么做。