The suggested solution mentioned an algorithm which is very similar to my initial thought : heapfy the whole input array into a minimum heap and then popup minimum for k times. To heapfy an array of length n will take O(2n) (the factor is 2),so this solution will take O(2n + k 2 logn) time. Let's call it option1.
My initial thought is to heapfy first k elements into a maximum heap and then compare the top element with each following input element to decide whether to remove and the top and insert the new one(see my previous article). So the time complexity of this solution will be O(2k + (n-k) 2 logk ). Let's call it option2.
Suppose k is a certain fixed number , so if only logk > 1 ( k>2) , the option1 should outperform the option2.
Java Implementation:
public class KSmallestA { public static void main(String[] args) { assertEquals(new int[]{1,2,3,4}, getKSmallest(new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, 4)); assertEquals(new int[]{1,2,3,4}, getKSmallest(new int[]{10, 9, 8, 7, 6, 5, 4, 3, 2, 1}, 4)); assertEquals(new int[]{21,22,14,18,9}, getKSmallest(new int[]{27, 14, 18, 22, 21, 91, 33, 36, 42, 78 , 9, 65, 101, 29}, 5)); } private static void assertEquals(int[] standard, int[] result) { Arrays.sort(standard); Arrays.sort(result); assert Arrays.equals(standard, result); } public static int[] getKSmallest(int[] nums , int k) { MinIntHeap heap = new MinIntHeap(nums, 0 , nums.length); int[] result = new int[k]; for (int i = 0 ; i < k ; i ++ ) { result[i] = heap.pop(); } return result; } } class MinIntHeap { private int[] nums; private int count; public MinIntHeap ( int[] nums, int offset, int count){ this.nums = new int[count+1]; // index 0 will not be used System.arraycopy(nums, offset, this.nums, 1, count); this.count = count; for ( int i = count/2 ; i > 0 ; i --) { swimDown(i); } } public int[] getAll() { int result[] = new int[count]; System.arraycopy(this.nums, 1, result, 0, count); return result; } private void swimUp (int i) { int parent = i/2; while (parent != 0 && nums[i] < nums[parent]) { swap ( i, parent); i = parent; parent = i/2; } } private void swimDown(int i) { int lchild = i * 2; if ( lchild > count ) return; int smaller = lchild; int rchild = lchild + 1; if (rchild <= count && nums[rchild] < nums[lchild]) smaller = rchild; while( nums[smaller] < nums[i]) { swap ( smaller, i); i = smaller; lchild = i * 2; if ( lchild > count ) return; smaller = lchild; rchild = lchild + 1; if (rchild <= count && nums[rchild] < nums[lchild]) smaller = rchild; } } private void swap (int i , int j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } public int peek() { return nums[1]; } public int pop() { swap(1, count--); swimDown(1); return nums[count + 1]; } //don't concern resizing array here public void add (int num) { nums[++count] = num; swimUp(count); } }
相关推荐
373._Find_K_Pairs_with_Smallest_Sums查找和最小的k对数字【LeetCode单题讲解系列】
标题 "the kth smallest elem" 暗示我们要讨论的是如何在数组或集合中找到第k小的元素,这是一个常见的算法问题,在计算机科学和数据结构领域具有重要意义。描述中提到的 "Clion" 是一个流行的C/C++集成开发环境,...
java java_leetcode题解之Find K Pairs with Smallest Sums.java
java java_leetcode题解之Find K-th Smallest Pair Distance.java
"smallest-width"这个概念正是Android系统提供的一种解决方案,用于帮助开发者创建能够适应不同屏幕尺寸的应用。本文将深入探讨"smallest-width"的概念,以及如何利用它来实现Android自定义`dimens.xml`文件,以适应...
代码:// find K-th Smallest Pair Distancepublic int smallestDistancePair(int[] nums
378.Kth_Smallest_Element_in_a_Sorted_Matrix有序矩阵中第K小的元素【LeetCode单
在编程领域,"k-th Smallest element in an array" 是一个常见的问题,它涉及到排序、查找和算法效率等核心概念。在这个问题中,目标是找到一个整数数组中第k小的元素,其中k是一个正整数。这个问题在数据结构和算法...
CP2K是一款开源程序,主要用于基于密度泛函理论(DFT)的量子化学和固体物理计算。CP2K特别擅长于利用第一原理方法模拟分子动力学,尤其是在大的生物分子、固体材料以及表面科学等领域中,CP2K可以进行从头算分子...
python python_leetcode题解之2413_Smallest_Even_Multiple.py
c++ C++_leetcode题解之744. Find Smallest Letter Greater Than Target.cpp
C程序,计算n个整数序列中的第k个最小数字。 该程序将最多进行9次计数排序,每个数字位置一次。 第一种将对“百毫”数字进行运算。 最后一种排序将对“一个”数字进行操作(MSD基数排序受启发)。 每种分类都...
AT_code_festival_2017_qualb_f Largest Smallest Cyclic Shift 的 AC 代码
c c语言_leetcode题解之0230_kth_smallest_element_in_a_bst
将您的过程解决方案编码到lib/smallest_multiple.rb文件中。 将您的面向对象的解决方案编码到lib/oo_smallest_multiple.rb文件中。 运行learn直到所有RSpec测试通过。 来源 -- 在Learn.co上查看并开始免费学习编码。
在这个名为"the-smallest-tree.rar_The Tree"的压缩包中,包含了关于最小生成树算法的源代码,采用的是Visual C++ 6.0编程环境。 在图论中,一个无向图的最小生成树是指包含图中所有顶点的一个子图,且该子图是树形...
Exercise 8: Arrays 1. Write a program that reads ten numbers supplied by the user into a single subscripted array, and then prints out the ... Use the smallest possible array to solve this problem.
"smallest3hq"可能指的是C8051F单片机的最小系统设计,该设计通常包括电源、晶振、复位电路以及必要的I/O接口。在C语言编程中,我们需要初始化这些硬件资源,如设置时钟频率、配置I/O口等。 五、实践与研究 ...
一个用100行代码实现h264格式视频的编码器; 适合想了解参数在NAL中具体写入的同仁;
1. Write a program that reads ten numbers supplied by the user into a single subscripted array, and then prints out the average of them. ... Use the smallest possible array to solve this problem.