package arrays;

import java.util.ArrayList;
import java.util.PriorityQueue;

/**
 * 题目: 数组中最小的 K 个数
 *
 * @Author Gavin
 * @date 2022年08月06日 15:52
 */
public class array_23 {
 /**
 * 第一种方法:使用一个大小为k的大顶堆(默认是小顶堆[从小到大输出])
 */
 //O(NlogK) + O(K)
 public ArrayList<Integer> solution(int[] nums, int k) {
 if (k > nums.length || k <= 0)
 return new ArrayList<>();
 PriorityQueue<Integer> maxHeap = new PriorityQueue<>((o1, o2) -> o2 - o1);
 for (int num : nums) {
 maxHeap.add(num);
 if (maxHeap.size() > k)
 maxHeap.poll();
 }
 return new ArrayList<>(maxHeap);
 }
 /**
 * 第二种方法:选择排序
 */
 //利用选择排序
 public ArrayList<Integer> solution_2(int[] nums, int k) {
 ArrayList<Integer> result = new ArrayList<>();
 getByFastAsc(nums);//传递的是引用,所以nums里面已经排序了
 for (int i = 0; i < k; i++) {
 result.add(nums[i]);
 }
 return result;
 }

 public void getByFastAsc(int[] arr) {
 for (int i = 0; i < arr.length - 1; i++) {//控制循环次数
 int min = i;//最小索引
 for (int j = i + 1; j < arr.length; j++) {//从无序区选取最小的记录
 if (arr[min] > arr[j]) {//如果最小数索引的数比后面的数大就和该数交换索引
 min = j;//交换索引,循环重复后得出最小的数的索引
 }
 }
 if (min != i) {//如果最小数的索引和一开始引用的数的索引不想等,那么就做一个替换。
 int temp = arr[i];//把一开始引用的数传给中间介质,也就是较大值
 arr[i] = arr[min];//把最小数传到一开始定位的位置
 arr[min] = temp;//把中间介质传给最小数,把大值赋值给min位置
 }
 }
 }
}