Tag Archives: 算法

求单向链表倒数第 k 个结点

题目:输入一个单向链表,输出该链表中倒数第 k 个结点。

传统做法是获取到链表的长度n,然后走n-k布,此方法弱爆了……

做法:

1、指定一个新的指针,走k步。如果k布之内就到了NULL,显然无倒数第k这说法,返回错误即可。

2、新指针到位后,和root一起next,知道新指针到了NULL。此时输出root指针当前的data即可。

 

找唯一重复的元素

1-1000放在含有1001个元素的数组中,只有唯一的一个元素值重复,其它均只出现一次。每个数组元素只能访问一次,设计一个算法,将它找出来;不用辅助存储空间,能否设计一个算法实现?

普通青年解法:

1+2+….+1000->5050

a1+a2+….+a1001->X

x – 5050 -> n(重复)

文艺青年解法:

a1^a2^…..a1001 = n(对所有的元素求一遍异或,就是最终重复的元素)

证明也不复杂,见:[……]

继续阅读

关于Random Shuffling算法。

其实就是随机洗牌。

Knuth给过一个算法,为代码如下:

注意:随机数不是1~n,而是i~n!!

关于为什么如此,吾等码农就不了解了,等大神来证明吧……

大量数据取k个最大值并排序

需求是这样的,我们都知道,在信息检索中,经常要取top-k(一共k,而不是第k)个得分最大的文档,并且从大到小排序。

而且文档规模很大,最少也要上千万。

话说这是一道很可以拿来面试的题啊。

我们不考虑Hadoop神马的,就说说单机怎么搞。

最傻的做法就是把1000万个都存储下来,然后sort,然后取min(k, vec.size())。

这样有两个缺点:
1、内存占用非常大,其实我们只要保留最大的1000个,但这样就要保存N个。在1000万的测试中,它要占用68M[……]

继续阅读