企业高端网站建设,公司网站如何被收录,重庆学校网站推广,百度广告联盟入口最小的k个数
题目#xff1a;输入n个整数#xff0c;找出其中最小的k个数#xff0c;例如输入4,5#xff0c;6,7#xff0c;8,9这六个数字#xff0c;则最小的4个是4,5#xff0c;6,7
方案一
还是最直观的方法#xff0c;先排序#xff0c;最快的是快排O(nlog2n)输入n个整数找出其中最小的k个数例如输入4,56,78,9这六个数字则最小的4个是4,56,7
方案一
还是最直观的方法先排序最快的是快排O(nlog2n)然后遍历前面k个数组得到我们需要的答案这个最简单方案应该有更优实现
方案二
题意我们需要找出最小的k个数字还是从快排的思路收到启发我们同样基于快速排序但是只找出第k个大的数字因为快排过程中会将比基准值小的放到 之前比基准值大的放到后面因此只需要找到第k个大的数字在之前的数就是我们需要的数基于如上分析有如下代码
/*** 找出数组中最小的K个数** author liaojiamin* Date:Created in 10:18 2021/6/16*/
public class GetLeastNumbers {public static void main(String[] args) {Integer[] arrayData new Integer[20];Random random new Random();for (int i 0; i 20; i) {arrayData[i] random.nextInt(50);System.out.print(arrayData[i],);}System.out.println();Integer[] newArray getLeastNumbers(arrayData, 10);for (Integer integer : newArray) {System.out.print(integer,);}}/*** 按快速排序思路找到第k个大的数将小的放k前面* 将大的放k后得到数组中最小的k个数就是下标是0~k的所有数*/public static Integer[] getLeastNumbers(Integer[] array, Integer key) {if (array null || array.length 0 || array.length key) {return new Integer[]{};}if (array.length key) {return array;}return quickSort(array, 0, array.length-1, key);}public static Integer[] quickSort(Integer[] array, Integer left, Integer right, Integer key) {if (left right) {Integer middle quickSortSwap(array, left, right);if (middle key) {return Arrays.copyOfRange(array, 0, key);}quickSort(array, left, middle - 1, key);quickSort(array, middle 1, right, key);}return Arrays.copyOfRange(array, 0, key);}public static Integer quickSortSwap(Integer[] array, Integer left, Integer right) {if (left right) {Integer position array[left];while (left right) {while (left right array[right] position) {right--;}if (left right) {array[left] array[right];left;}while (left right array[left] position) {left;}if(left right){array[right] array[left];right --;}}array[left] position;}return left;}
}
基于快排的方案是有限制的因为我们需要修改输入的数组最后的顺序是变化的如果要求不能修改输入的参数我们是否有其他方案。
方案三
既然不能修改原值那么我们复制一个我们需要的值还是空间换时间的做法我们建一个原数组大小的容器用来存储接着在容器中找出最小的k个数本次我们需要的存储的特点是能快速的找到最小值这样重复查找k次最小值就能得到结果如果我们用二叉查找树来实现这个容器那么我们每次查询的时间复杂度是O(logn)也就是层高度那么k次查询就是O(klogn)但是还有其他变种的二叉查找树二叉堆中对小堆之前文章数据结构与算法–二叉堆最大堆最小堆实现及原理对最大堆最小堆的实现有详细的解释最小堆的特点在于能在O(1)时间内找到最小值就是二叉堆的根节点并且二叉堆的结构特性就在于能够快速的查询我们将所有数据构造成一个最小堆然后经k次O(1)的操作就能得到结果经如上分析有如下代码
/*** 找出数组中最小的K个数** author liaojiamin* Date:Created in 10:18 2021/6/16*/
public class GetLeastNumbers {public static void main(String[] args) {Integer[] arrayData new Integer[20];Random random new Random();for (int i 0; i 20; i) {arrayData[i] random.nextInt(50);System.out.print(arrayData[i],);}System.out.println();Integer[] heapArray getLeastNumbersByBinaryHeapMax(arrayData, 10);for (int i 0; i heapArray.length; i) {System.out.print(heapArray[i],);}}/*** 利用二叉堆最小堆的结构特性构建最小堆后每次去跟节点都是最小的节点* 循环取k个最小堆中根元素得到我们的结果* */public static Integer[] getLeastNumbersByBinaryHeapMax(Integer[] array, Integer key){if (array null || array.length 0 || array.length key) {return new Integer[]{};}if (array.length key) {return array;}Integer size (array.length 2 )*11/10;BinaryHeap binaryHeap new BinaryHeap(size);for (int i 0; i array.length; i) {binaryHeap.insert(new AnyType(array[i]));}Integer[] result new Integer[key];for (Integer i 0; i key; i) {result[i] Integer.valueOf(binaryHeap.deleteMin().getElement().toString());}return result;}
}
方案四
如上最小堆的实现中虽然找最小值都是O(1)但是在构造最小堆的过程中我们需要O(logn)的时间复杂度如果题目要是海量数据其实我们也可以用最大堆我们可以用k个元素的最大堆当堆满后每次读入原数组中一个数据与最大数据比较O(1)时间如果比最大数据要小我们删除最大数据插入当前值直到整个数组遍历完此时得到的最大堆中k个数据就是我们需要的数据这种方案可以用来处理海量数据时候内存占用过多的问题。海量数据情况下空间复杂度O(k)的实现方式如下
/*** 找出数组中最小的K个数** author liaojiamin* Date:Created in 10:18 2021/6/16*/
public class GetLeastNumbers {public static void main(String[] args) {Integer[] arrayData new Integer[20];Random random new Random();for (int i 0; i 20; i) {arrayData[i] random.nextInt(50);System.out.print(arrayData[i],);}System.out.println();Integer[] maxArray getLeastNumberByBinaryHeapMax(arrayData, 10);for (Integer integer : maxArray) {System.out.print(integer,);}}/*** 利用二叉堆最大堆处理海量数据情况下获取前k个最小的数据* */public static Integer[] getLeastNumberByBinaryHeapMax(Integer[] array, Integer key){if (array null || array.length 0 || array.length key) {return new Integer[]{};}if (array.length key) {return array;}Integer size (array.length2)*11/10;BinaryHeapMax binaryHeapMax new BinaryHeapMax(size);for (int i 0; i array.length; i) {AnyType anyType new AnyType(array[i]);if(binaryHeapMax.heapSize() key){Integer heapMax Integer.valueOf(binaryHeapMax.findMax().getElement().toString());if(array[i] heapMax){binaryHeapMax.deleteMax();binaryHeapMax.insert(anyType);}}else {binaryHeapMax.insert(anyType);}}AnyType[] anyTypes binaryHeapMax.getAppHeapData();Integer[] result new Integer[key];for (int i 0; i anyTypes.length; i) {result[i] Integer.valueOf(anyTypes[i].getElement().toString());}return result;}
}
解法对比
第一种方案直接排序遍历平均时间复杂度是O(nlog2n)比第二种思路上更容易理解但是同时也有明显的限制会修改入参数组第二种解法也是基于快排思路但是可以在中间退出因此时间复杂度小于O(nlog2n)同样也会修改入参数组第三种方法最小堆的方式先构建最小堆在读取这种有两个明显优点一个是没有修改输入的数据因为我们只是读取入参数组中的数字所有写操作都是在最小堆中完成二是解法简单缺点也明显时间复杂度更大构建时候需要insertn次每次insert的平均时间复杂度是O(logn)因此是O(nlogn)第四种算法适合海量数据的输入如果题目要求的是海量数数据中找k个数内存的大小限制不可能全读取如内存这时候我们只一次读取一个数据进内存只要求内存容纳的下最大堆中的k个数据即可能有效解决n很大k很小的情况时间复杂度也是O(nlogk)
上一篇数据结构与算法–两个链表中第一个公共节点 下一篇数据结构与算法–数字在排序数组中出现次数
