第K大数算法分析、设计与实现(Java)
问题描述:有一个大小为n的数组A[0,1,2,…,n-1],求其中第k大的数。 ? 策略: (1)?? 判断问题的性质,是排序型?最优型?其他? (2)?? 根据不同类型的问题挑选不同的算法。“已知算法->递归->分治->贪心->回溯法->分支限界法->动态规划->算法设计” (3)?? 根据相应的算法进行分析 ? ? 目录 0,分析输入输出... 1 1,分析算法... 1 2,时间复杂度与空间复杂度... 2 3,测试结果... 2 4,代码... 3 ? ? ? 0,分析输入输出这个问题并不限制输入输出,既可以是网络环境,也可以是其他环境。 网络环境下一般采用的都是流式算法,其他环境一般都是数据齐全的。 故可以将该问题的输入输出分为两大类:流型,稳定型 1,分析算法该问题并不是最优型,不是那种求最优值、最优解的问题(如:背包问题)。而是排序型 ? (1)先从稳定型的入手: 看到球第K大数这个标题,第一想法就是:排序 ①???? 完全排序: 一上来先给这堆数据来个排序,什么排序都行,只要够快,然后直接从数据中取第K大的就可以了。 ? A完全排序 B输出第K大数 ②???? 不完全排序: 对于不重复使用的数据来说,完全排序太过于浪费,一般只需要排到第K个数。这里可以使用冒泡排序 ? A使用冒泡排序 B循环K次 C输出第K大数 ③???? 分治: 按照上面的想法,既然第K大数后面的数没有用,那么也有可能第K大数前面的数也没什么用。只需要找出第K大数就可以了,于是可以用快速分治来取得第K大数。这种思想类似于二分法 ? A通过快速排序,选择数X,进行一轮降序排序 B判断X的位置是否刚好是第K位,若是则直接输出;否则执行C C若X的位置大于K,则选择[0,X)进行下一轮排序;否则取得(X,n]进行下一轮 D若找到第K大数则直接输出 (2)流型: ??? 网络环境下,数据的长度是不稳定的,如果K不是很大的话,可以创建一个大小为K的数组,将数据往里套,超出范围的数据直接抛弃。第K个位置的数据即为第K大数 ??? A创建大小为K的数组,每个元素都赋值为整数最小值,以保证数据能正常进行判断 B每当有数据时,将数据插入到数组中,维持有序。 C当需要输出第K大数时,直接输出第K位置的数据。 2,时间复杂度与空间复杂度(1)?? 在有序的情况下选取第K大数 ①? 完全排序:O(n*logn),内存占用n,适合反复求取同一组数的第XX大数的情况。但k>logn ②? 不完全排序:O(n*k),内存占用n,适合反复求取同一组数的第XX大数的情况。但k<logn (2)?? 在无序的情况下选取第K大数 ①? 流型:O(n*k),内存占用k,适合网络流式的第XX大数计算,计算完后不保存N个数 ②? 分治型:O(n),内存占用n 3,测试结果选取随机数范围:0~10000。数组中数的个数N,测试次数M,目标K
? 显然:在N<1000且M、K较小时,更适合使用流型。 但随着运算次数,运算数量级的增加,流型将会大量占用分配内存,导致明显的速度的下降。(这是在本机上会出现问题,因为涉及到不断地资源分配,但在网络环境下只会用到一个大小为K的数组) 分治型的表现最为优秀,无论是数量级的增加,还是计算次数的增加,都能很好保证较优的计算效率。 完全排序则更适合反复求第XX大(小)的情况。例如:数据库 ? 4,代码package divideAndConquer; import java.util.Date; import java.util.Random; /** * 输入N个数,输出第K大数 * @Input N K N个数 * @Output第K大数 * */ public class FindK { public static void main(String[] args) { Random random = new Random(newDate().getTime()); int N = 1000; // 待查询数组 int MAX = 10000; // int K = 800; // 目标数 int[] nums = new int[N]; for (int i = 0; i < N; i++) { nums[i] = random.nextInt(MAX); } // System.out.print("处理前:" + Arrays.toString(nums)); System.out.println(); System.out.println(); int M = 100000; /* 有序 */ // 完全排序 // System.out.println("完全排序:" + findKBySort(nums.clone(),K)); long t1 = System.currentTimeMillis(); for (int i = 0; i < M; i++) { findKBySort(nums.clone(),K); } long t2 = System.currentTimeMillis(); System.out.println("耗时:" + (t2 - t1)); // 不完全排序 // System.out.println("不完全排序:" + findKByBubbleSort(nums.clone(),K)); t1 = System.currentTimeMillis(); for (int i = 0; i < M; i++) { findKByBubbleSort(nums.clone(),K); } t2 = System.currentTimeMillis(); System.out.println("耗时:" + (t2 - t1)); /* 无序 */ // 插入法 // System.out.println("插入法:" + findKByArray(nums.clone(),K)); t1 = System.currentTimeMillis(); for (int i = 0; i < M; i++) { findKByArray(nums.clone(),K); } t2 = System.currentTimeMillis(); System.out.println("耗时:" + (t2 - t1)); // 快速分治 // System.out.println("快速分治:" // + findKByDivAndConq(nums.clone(),nums.length - 1,K)); t1 = System.currentTimeMillis(); for (int i = 0; i < M; i++) { findKByDivAndConq(nums.clone(),K); } t2 = System.currentTimeMillis(); System.out.println("耗时:" + (t2 - t1)); } /** * 先排序,后取得第K大数 */ public static int findKBySort(int[] nums,int K) { quickSort(nums,false);// 降序排序 return nums[K - 1]; } /** * 快速排序: * * @param nums 整型数组 * @param orient true则升序,false则降序 */ public static void quickSort(int[] nums,int fromIndex,int toIndex,boolean orient) { if (nums == null || fromIndex >= toIndex) return; int temp = 0; int mid = (fromIndex + toIndex) / 2; int midNum = nums[mid]; int a = fromIndex,b = toIndex; while (a < b) { if (orient) { while (nums[a] <= midNum && a < mid) { a++; } while (nums[b] >= midNum && b > mid) { b--; } } else { while (nums[a] >= midNum && a < mid) { a++; } while (nums[b] <= midNum && b > mid) { b--; } } if (a == mid) { mid = b; } else if (b == mid) { mid = a; } temp = nums[a]; nums[a] = nums[b]; nums[b] = temp; } quickSort(nums,fromIndex,mid - 1,orient); quickSort(nums,mid + 1,toIndex,orient); } /** * 冒泡排序取得第K大数,只需循环K次,取得前K个数即可 */ public static int findKByBubbleSort(int[] nums,int K) { int temp = 0; for (int i = 0; i < K; i++) { for (int j = nums.length - 1; j > i; j--) { if (nums[j - 1] < nums[j]) { temp = nums[j - 1]; nums[j - 1] = nums[j]; nums[j] = temp; } } } return nums[K - 1]; } /** * 创建大小为K的数组,并不断将数据有序插入数组中,最后取得第K个数 */ public static int findKByArray(int[] nums,int K) { int[] array = new int[K];// 创建大小为K的数组 // 将数据有序插入数组 int count = 1;// array 中有效数的个数 int index = 0; array[0] = nums[0]; for (int i = 1; i < nums.length; i++) { if (nums[i] >= array[count - 1]) {// if (count < K) { array[count] = array[count - 1]; } index = count - 2; while (index >= 0&& nums[i] >= array[index]) {// 数组后移一位 array[index + 1] = array[index]; index--; } array[index + 1] = nums[i];// 插入 if (count < K) {// count++; } } else { if (count < K) { array[count] = nums[i]; count++; } } } return array[K - 1]; } /** * 快速分治法,求第K大数。根据一个数,将数组中所有数进行快速排序,使得该数下标前的数大于该数,下标后的数小于该数 */ public static int findKByDivAndConq(int[] nums,int K) { int a = fromIndex,b = toIndex; int midIndex = a; while (a < b) { while (a < b && nums[b] <= nums[midIndex]) { b--; } swap(nums,midIndex,b); midIndex = b; while (a < b && nums[a] >= nums[midIndex]) { a++; } swap(nums,a); midIndex = a; } if (midIndex > K - 1) { return findKByDivAndConq(nums,midIndex - 1,K); } else if (midIndex < K - 1) { return findKByDivAndConq(nums,midIndex + 1,K); } else { return nums[midIndex]; } } /** * 交换 * */ public static void swap(int[] nums,int a,int b) { int temp = nums[a]; nums[a] = nums[b]; nums[b] = temp; } } ? ? 总结:在本机上或许分治型的更为合适,这是因为数据的齐全的,但在网络环境下流型的更为合适。网络环境下的数据虽然不断增加,但是一直都使用着同一个大小为K的数组 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |