在前一篇讲选择数问题时,使用了一种类似于快速排序的算法来解决选择数问题,见:http://www.iflym.com/index.php/code/201108240001.html。
而根据算法导论上的一种最坏时间为O(n)的一种解法,其详细的步骤如下所示:
- 将数组s按5个为一组,划分成不同的小组,小组数
- 对每个小组,进行插入排序,并选择其中的中位数
- 将每个小组的中位数,组成一个新的数组,并递归的选择出最终的中位数m
- 以m作为参照数,将数组s划分成两个部分,使得m所处的位置数比左侧的数目大1
- 如果左侧的数目数恰好为寻找的第k位数,则m即为我们要找的数,否则继续在左侧或者右侧进行查找
有了几个的思路,具体算法就很简单了。参考代码如下所示:
private static int find2(int[] ints, int k, int start, int end) { //如果k为1,则寻找最小数,如果k为end-start+1则寻找最大数 //总长度小于5,直接插入排序并查找 ...... //寻找到中位数 int z = findMiddle(ints, start, end); //按中位数分割数组,其中ints[divide]=z int divide = divide(ints, z, start, end); //判断在哪个部分 int frontNum = divide - start; //恰好为中位数 if(frontNum == k - 1) return ints[divide]; //高部分 if(frontNum < k) return find2(ints, (k - frontNum), divide + 1, end); //低部分 return find2(ints, k, start, divide - 1); }
中间有几个函数值得注意,首先即是寻找中位数的算法,代码如下所示:
/** 寻找中位数 */ private static int findMiddle(int[] ints, int start, int end) { //按5进行分组 int sum = end - start + 1; if(sum <= 5) { charuSort(ints, start, end); return ints[start + calcMiddleSum(start, end)]; } int z = sum / 5; z = sum % 5 == 0 ? z : z + 1; //另开数组用于存储每组的中位数 int[] aints = new int[z]; //每组插入排序 for(int i = 0;i < z;i++) { int zStart = i * 5; if(i == z - 1) { charuSort(ints, zStart, end); aints[i] = ints[zStart + calcMiddleSum(end, zStart)]; } else { charuSort(ints, zStart, zStart + 5); aints[i] = ints[zStart + 2]; } } return findMiddle(aints, 0, z - 1); }
以上即为算法为O(n)的算法参考实现,当然本实现的未必是最优的,也可能达不到《算法导论》中O(N)的运行效率,仅给一个实现参考。
本实现,支持数组中重复的数字,这是在《算法导论》中被回避的一节(文中假设所有数都不相同)。
转载请标明出处:i flym
本文地址:https://www.iflym.com/index.php/code/201110120001.html