• 一、题目
  • 二、解题思路
  • 三、解题代码

    一、题目

    输入n个整数,找出其中最小的k个数。

    例子说明:

    例如输入4 、5 、1、6、2、7、3 、8 这8 个数字,则最小的4 个数字是1 、2、3 、4

    二、解题思路

    解法一:O(n)时间算法,只有可以修改输入数组时可用。

    可以基于Partition函数来解决这个问题。如果基于数组的第k个数字来调整,使得比第k个数字小的所有数字都位于数组的左边,比第k个数字大的所有数字都位于数组的右边。这样调整之后,位于数组中左边的k个数字就是最小的k 个数字(这k 个数字不一定是排序的〉。

    解法二: O(nlogk)的算法,精剧适合处理海量数据。

    先创建一个大小为k的数据容器来存储最小的k个数字,接下来我们每次从输入的n个整数中读入一个数.如果容器中已有的数字少于k个,则直接把这次读入的整数放入容器之中:如果容器中己有k 数字了,也就是容器己满,此时我们不能再插入新的数字而只能替换已有的数字。找出这己有的k 个数中的最大值,然后1在这次待插入的整数和最大值进行比较。如果待插入的值比当前己有的最大值小,则用这个数替换当前已有的最大值:如果待插入的值比当前已有的最大值还要大,那么这个数不可能是最小的k个整数之一,于是我们可以抛弃这个整数。

    因此当容器满了之后,我们要做3 件事情: 一是在k 个整数中找到最大数: 二是有可能在这个容器中删除最大数: 三是有可能要插入一个新的数字。我们可以使用一个大顶堆在O(logk)时间内实现这三步操作

    三、解题代码

    1. public class Test {
    2. /**
    3. * 大顶堆
    4. *
    5. * @param <T> 参数化类型
    6. */
    7. private final static class MaxHeap<T extends Comparable<T>> {
    8. // 堆中元素存放的集合
    9. private List<T> items;
    10. // 用于计数
    11. private int cursor;
    12. /**
    13. * 构造一个椎,始大小是32
    14. */
    15. public MaxHeap() {
    16. this(32);
    17. }
    18. /**
    19. * 造诣一个指定初始大小的堆
    20. *
    21. * @param size 初始大小
    22. */
    23. public MaxHeap(int size) {
    24. items = new ArrayList<>(size);
    25. cursor = -1;
    26. }
    27. /**
    28. * 向上调整堆
    29. *
    30. * @param index 被上移元素的起始位置
    31. */
    32. public void siftUp(int index) {
    33. T intent = items.get(index); // 获取开始调整的元素对象
    34. while (index > 0) { // 如果不是根元素
    35. int parentIndex = (index - 1) / 2; // 找父元素对象的位置
    36. T parent = items.get(parentIndex); // 获取父元素对象
    37. if (intent.compareTo(parent) > 0) { //上移的条件,子节点比父节点大
    38. items.set(index, parent); // 将父节点向下放
    39. index = parentIndex; // 记录父节点下放的位置
    40. } else { // 子节点不比父节点大,说明父子路径已经按从大到小排好顺序了,不需要调整了
    41. break;
    42. }
    43. }
    44. // index此时记录是的最后一个被下放的父节点的位置(也可能是自身),所以将最开始的调整的元素值放入index位置即可
    45. items.set(index, intent);
    46. }
    47. /**
    48. * 向下调整堆
    49. *
    50. * @param index 被下移的元素的起始位置
    51. */
    52. public void siftDown(int index) {
    53. T intent = items.get(index); // 获取开始调整的元素对象
    54. int leftIndex = 2 * index + 1; // // 获取开始调整的元素对象的左子结点的元素位置
    55. while (leftIndex < items.size()) { // 如果有左子结点
    56. T maxChild = items.get(leftIndex); // 取左子结点的元素对象,并且假定其为两个子结点中最大的
    57. int maxIndex = leftIndex; // 两个子节点中最大节点元素的位置,假定开始时为左子结点的位置
    58. int rightIndex = leftIndex + 1; // 获取右子结点的位置
    59. if (rightIndex < items.size()) { // 如果有右子结点
    60. T rightChild = items.get(rightIndex); // 获取右子结点的元素对象
    61. if (rightChild.compareTo(maxChild) > 0) { // 找出两个子节点中的最大子结点
    62. maxChild = rightChild;
    63. maxIndex = rightIndex;
    64. }
    65. }
    66. // 如果最大子节点比父节点大,则需要向下调整
    67. if (maxChild.compareTo(intent) > 0) {
    68. items.set(index, maxChild); // 将子节点向上移
    69. index = maxIndex; // 记录上移节点的位置
    70. leftIndex = index * 2 + 1; // 找到上移节点的左子节点的位置
    71. } else { // 最大子节点不比父节点大,说明父子路径已经按从大到小排好顺序了,不需要调整了
    72. break;
    73. }
    74. }
    75. // index此时记录是的最后一个被上移的子节点的位置(也可能是自身),所以将最开始的调整的元素值放入index位置即可
    76. items.set(index, intent);
    77. }
    78. /**
    79. * 向堆中添加一个元素
    80. *
    81. * @param item 等待添加的元素
    82. */
    83. public void add(T item) {
    84. items.add(item); // 将元素添加到最后
    85. siftUp(items.size() - 1); // 循环上移,以完成重构
    86. }
    87. /**
    88. * 删除堆顶元素
    89. *
    90. * @return 堆顶部的元素
    91. */
    92. public T deleteTop() {
    93. if (items.isEmpty()) { // 如果堆已经为空,就报出异常
    94. throw new RuntimeException("The heap is empty.");
    95. }
    96. T maxItem = items.get(0); // 获取堆顶元素
    97. T lastItem = items.remove(items.size() - 1); // 删除最后一个元素
    98. if (items.isEmpty()) { // 删除元素后,如果堆为空的情况,说明删除的元素也是堆顶元素
    99. return lastItem;
    100. }
    101. items.set(0, lastItem); // 将删除的元素放入堆顶
    102. siftDown(0); // 自上向下调整堆
    103. return maxItem; // 返回堆顶元素
    104. }
    105. /**
    106. * 获取下一个元素
    107. *
    108. * @return 下一个元素对象
    109. */
    110. public T next() {
    111. if (cursor >= items.size()) {
    112. throw new RuntimeException("No more element");
    113. }
    114. return items.get(cursor);
    115. }
    116. /**
    117. * 判断堆中是否还有下一个元素
    118. *
    119. * @return true堆中还有下一个元素,false堆中无下五元素
    120. */
    121. public boolean hasNext() {
    122. cursor++;
    123. return cursor < items.size();
    124. }
    125. /**
    126. * 获取堆中的第一个元素
    127. *
    128. * @return 堆中的第一个元素
    129. */
    130. public T first() {
    131. if (items.size() == 0) {
    132. throw new RuntimeException("The heap is empty.");
    133. }
    134. return items.get(0);
    135. }
    136. /**
    137. * 判断堆是否为空
    138. *
    139. * @return true是,false否
    140. */
    141. public boolean isEmpty() {
    142. return items.isEmpty();
    143. }
    144. /**
    145. * 获取堆的大小
    146. *
    147. * @return 堆的大小
    148. */
    149. public int size() {
    150. return items.size();
    151. }
    152. /**
    153. * 清空堆
    154. */
    155. public void clear() {
    156. items.clear();
    157. }
    158. @Override
    159. public String toString() {
    160. return items.toString();
    161. }
    162. }
    163. /**
    164. * 题目: 输入n个整数,找出其中最小的k个数。
    165. * 【第二种解法】
    166. * @param input 输入数组
    167. * @param output 输出数组
    168. */
    169. public static void getLeastNumbers2(int[] input, int[] output) {
    170. if (input == null || output == null || output.length <= 0 || input.length < output.length) {
    171. throw new IllegalArgumentException("Invalid args");
    172. }
    173. MaxHeap<Integer> maxHeap = new MaxHeap<>(output.length);
    174. for (int i : input) {
    175. if (maxHeap.size() < output.length) {
    176. maxHeap.add(i);
    177. } else {
    178. int max = maxHeap.first();
    179. if (max > i) {
    180. maxHeap.deleteTop();
    181. maxHeap.add(i);
    182. }
    183. }
    184. }
    185. for (int i = 0; maxHeap.hasNext(); i++) {
    186. output[i] = maxHeap.next();
    187. }
    188. }
    189. /**
    190. * 题目: 输入n个整数,找出其中最小的k个数。
    191. * 【第一种解法】
    192. * @param input 输入数组
    193. * @param output 输出数组
    194. */
    195. public static void getLeastNumbers(int[] input, int[] output) {
    196. if (input == null || output == null || output.length <= 0 || input.length < output.length) {
    197. throw new IllegalArgumentException("Invalid args");
    198. }
    199. int start = 0;
    200. int end = input.length - 1;
    201. int index = partition(input, start, end);
    202. int target = output.length - 1;
    203. while (index != target) {
    204. if (index < target) {
    205. start = index + 1;
    206. } else {
    207. end = index - 1;
    208. }
    209. index = partition(input, start, end);
    210. }
    211. System.arraycopy(input, 0, output, 0, output.length);
    212. }
    213. /**
    214. * 分区算法
    215. *
    216. * @param input 输入数组
    217. * @param start 开始下标
    218. * @param end 结束下标
    219. * @return 分区位置
    220. */
    221. private static int partition(int[] input, int start, int end) {
    222. int tmp = input[start];
    223. while (start < end) {
    224. while (start < end && input[end] >= tmp) {
    225. end--;
    226. }
    227. input[start] = input[end];
    228. while (start < end && input[start] <= tmp) {
    229. start++;
    230. }
    231. input[end] = input[start];
    232. }
    233. input[start] = tmp;
    234. return start;
    235. }
    236. }