Question

问题:给定一组有序数组,要求从数组中找出满足ai>k的最小数。并输出最小数的

Answer 1

问：问题:给定一组有序数组,要求从数组中找出满足ai>k的最小数。并输出最小数的

答：亲亲您好，根据您的问题描述，这边经过查询并经过审慎分析，得出答案如下哦亲亲：输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。示例 1：输入：arr = [3,2,1], k = 2输出：[1,2] 或者 [2,1]示例 2：输入：arr = [0,1,2,1], k = 1输出：[0]限制：0 <= k <= arr.length <= 100000 <= arr[i] <= 10000 题目分析：首先这个问题，就是一个普通的排序问题： 排序分为选择排序，冒泡排序，插入排序，快速排序，基数排序，归并排序等;可以解决该问题。1）暴力算法：首先对于解决本题目，先想到使用冒泡排序，冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。 它的思路是先将数组进行排序，然后取前面k个值，最直接的思路：比较相邻的元素。如果第一个比第二个大，就交换它们两个；对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；针对所有的元素重复以上的步骤，除了最后一个；重复步骤1~3，直到排序完成。 排序完成之后再选取前面k个值： /** * 获取最小多个值;快速排序 * * @param arr 数组 * @param k k个数 * @return 数组 */

问：代码

答：亲亲您好，根据您的问题描述，这边经过查询并经过审慎分析，得出答案如下哦亲亲：# 最大堆下沉调整，始终保持最大堆def downAdjust(ary_list, parent_index, length): tmp = ary_list[parent_index] child_index = 2 * parent_index + 1 while child_index < length: if child_index + 1 length and ary_list[child_index + 1] > ary_list[child_index]: child_index += 1 if tmp >= ary_list[child_index]: break ary_list[parent_index] = ary_list[child_index] parent_index = child_index child_index = 2 * parent_index + 1 ary_list[parent_index] = tmp pass# 构建堆def build_heap(ary_list, k): index = k // 2 - 1 # 最后一个非叶子结点 while index >= 0: downAdjust(ary_list, index, k) index -= 1 pass# 利用最大堆找出前K个最小值# 每次从原数组中拿出一个元素和当前堆顶值比较，# 然后判断是否可以放入，放入后继续调整堆结构def heapK(ary, nums, k): if nums <= k: return nums ks = ary[:k] build_heap(ks, k) # 构建大顶堆（先不排序）