1. 排序，6000ms+，时间复杂度高，算法复杂度低，推荐。
2. 线段树+二分，2000ms，时间复杂度中，算法复杂度高，不推荐。
3. 经典第k元素算法，500ms-，时间复杂度低，算法复杂度中，推荐。

说说第3种算法。想了几天，终于领悟了所谓的 n*log(n) 复杂度算法，原来就是经典的第k元素算法的分治思想：查找一个序列的第k元素，先将其划分为两个子序列，判断第k元素在那个子序列中，转入相应子序列查找，故一次查找复杂度为log(n)。但要先构建划分树，每一次查找，通过查询划分树能在常数时间内决定第k元素在哪个划分第几个元素。这棵划分树非常类似于第二种算法使用的归并树。生成划分树时间复杂度 n*log(n)，所以总复杂度为 n * log(n) + m * log(n) = n * log(n)。

• Re:原来最好的算法，就是使用分治思想的经典第k元素算法 (158) accept123 2009-12-14 22:25:21
  • Re:原来最好的算法，就是使用分治思想的经典第k元素算法 (50) accept123 2009-12-14 23:43:10
    • Re:原来最好的算法，就是使用分治思想的经典第k元素算法 (1093) lengxiang 2010-08-09 11:15:18
    • Re:原来最好的算法，就是使用分治思想的经典第k元素算法 (0) fmh 2011-04-06 20:58:22
• Re:原来最好的算法，就是使用分治思想的经典第k元素算法 (26) godofwa2 2013-05-09 17:25:52
• Re:原来最好的算法，就是使用分治思想的经典第k元素算法 (21) 2805734199h 2021-10-05 16:09:40
• Re:原来最好的算法，就是使用分治思想的经典第k元素算法 (375) YoRHa_2B 2021-10-23 12:06:59