面试中被问的两个算法题

第二个用堆？第一个不会，等大牛回答 【 在 Jarod (学五608鬼魂) 的大作中提到: 】 : 似乎我都没答好。看有没有人给出好的想法。 : 1. NxN的棋盘，初始的时候在棋盘上放一些棋子，然后按规则“如果一个空位置上下左右四个紧相邻的位置中，有两个位置有棋子，则在这个位置也放上棋子”不断进行。问初始时，最少放几个棋子，位置如何，能按上面的规则把棋盘放满。 : 2.N为int，N>>k, 从N个不相同的数里选出前k小的数来。 感觉有点infer...但偶从来没有深究过这题，解法也很搓......... : ...................

第一题 我试验了一下 应该是N个肯定能做到。 能不能更少我就不知道了。 第二题只要排序就可以吧？快排、堆排。。。 快速选择算法有O(N)的 但只是理论界 一般使用还是使用O(N*logN)的算法吧

第二题比我给的解还差。。。。。。我第一反应是 O(Nk) 【 在 Grape 的大作中提到: 】 : 第一题 我试验了一下 应该是N个肯定能做到。 : 能不能更少我就不知道了。 : 第二题只要排序就可以吧？快排、堆排。。。 : ...................

选第K小的数的快速选择算法理论上界就是O(N) --平均运行时间（不是最坏运行时间） 如果是K个就是O(kN) 应该不会有更好的了 考虑到实际中编程起来方便，都还是用对数复杂度的。 你看你需要哪种？ 【 在 Jarod 的大作中提到: 】 : 第二题比我给的解还差。。。。。。我第一反应是 O(Nk)

选出前k小的数 ，用插入排序 O(n*k) ,堆的话就是 n*logk了

【 在 Jarod 的大作中提到: 】 : 似乎我都没答好。看有没有人给出好的想法。 : 1. NxN的棋盘，初始的时候在棋盘上放一些棋子，然后按规则“如果一个空位置上下左右四个紧相邻的位置中，有两个位置有棋子，则在这个位置也放上棋子”不断进行。问初始时，最少放几个棋子，位置如何，能按上面的规则把棋盘放满。 : 2.N为int，N>>k, 从N个不相同的数里选出前k小的数来。 感觉有点infer...但偶从来没有深究过这题，解法也很搓......... 第二题第一思路是用二分快排找第k小的元素。平均是O(n)，最坏是O(n^2) 算法导论有介绍最坏O（n）的算法，可以去看，基本原理也是快排的划分

.............你能把它的内容打出来么.................... 【 在 flyingmiao 的大作中提到: 】 : 第二题第一思路是用二分快排找第k小的元素。平均是O(n)，最坏是O(n^2) : 算法导论有介绍最坏O（n）的算法，可以去看，基本原理也是快排的划分

你没有算法导论么。 快排你知道吧？ 关键步骤是划分，大于哨兵的，小于哨兵的，而哨兵会站在它该属于的位置 快排两半都会继续划分 但找第k大元素的话，就像二分查找那样，只继续划分期中一半，直到找到第k大元素 【 在 Jarod 的大作中提到: 】 : .............你能把它的内容打出来么....................

如果k<<N ，感觉 选择排序 找出前K个小的就可以了~ 别拍我啊