选择数问题,最坏情况下时间为O(n)的算法实现参考

在前一篇讲选择数问题时,使用了一种类似于快速排序的算法来解决选择数问题,见:http://www.iflym.com/index.php/code/201108240001.html。
而根据算法导论上的一种最坏时间为O(n)的一种解法,其详细的步骤如下所示:

  1.     将数组s按5个为一组,划分成不同的小组,小组数
  2.     对每个小组,进行插入排序,并选择其中的中位数
  3.     将每个小组的中位数,组成一个新的数组,并递归的选择出最终的中位数m
  4.     以m作为参照数,将数组s划分成两个部分,使得m所处的位置数比左侧的数目大1
  5.     如果左侧的数目数恰好为寻找的第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

相关文章:

作者: flym

I am flym,the master of the site:)

发表评论

邮箱地址不会被公开。 必填项已用*标注