import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.*; public class Main { public static Scanner sc = new Scanner(System.in); public static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); public static long mod = (long)Math.pow(2,29); public static void main(String[] args) throws Exception { int n = sc.nextInt(); int k = sc.nextInt(); int[] arr = new int[n]; for(int i=0;i<n;i++) { int val = sc.nextInt(); arr[i] = val; } PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(); for(int i=0;i<n;i++){ priorityQueue.offer(arr[i]); } boolean flag = true; while (k-- > 0){ Integer topVal = priorityQueue.poll(); if(flag) { System.out.print(topVal); flag = false; }else { System.out.print(" " + topVal); } } System.out.println(); } // 大根堆，存储k个节点 // 大于根的忽略，小于根的 替换根，并更新堆 } /* 5 3 3 5 1 5 2 3 1 2 */
import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.*; class MyHeap{ int[] arr; int size; int capacity; public MyHeap(int k) { this.arr = new int[k+1]; // 1～ k 用来存元素 this.size = 0; this.capacity = k; } boolean isFull(){ return size == capacity; } // 自身全部调整 // void adjustSelf(){ // // 从 n/2 调整到 1 // for(int i=size/2; i >= 1; i--){ // int leftPos = i * 2; // int rightPos = i * 2 + 1; // if(leftPos <= size && rightPos <= size){ // if(arr[leftPos] > arr[i] && arr[rightPos] > arr[i]){ // if(arr[leftPos] > arr[rightPos]){ // swap(leftPos, i); // }else { // swap(rightPos, i); // } // }else if(arr[leftPos] > arr[i]){ // swap(leftPos, i); // }else if(arr[rightPos] > arr[i]){ // swap(rightPos, i); // }else { // continue; // } // }else if(leftPos <= size){ // if(arr[leftPos] > arr[i]){ // swap(leftPos, i); // } // }else { // continue; // } // } // } // 从下往上调整 void adjustDownToUp(int i){ while (i != 1){ int fa = i / 2; if(fa < 1){ break; } if(arr[i] < arr[fa]){ break; } swap(i, fa); i = fa; } } void swap(int posA, int posB){ int tmp = arr[posA]; arr[posA] = arr[posB]; arr[posB] = tmp; } // 从上往下不断到调整 void adjustUpToDown(int i){ // 从根开始往下调整 int leftPos = i * 2; int rightPos = i * 2 + 1; // 有一个还没到底，就不断到调整 while (leftPos <= size || rightPos <= size) { if (leftPos <= size && rightPos <= size) { if (arr[leftPos] > arr[i] && arr[rightPos] > arr[i]) { if (arr[leftPos] > arr[rightPos]) { swap(leftPos, i); i = leftPos; }else { swap(rightPos, i); i = rightPos; } }else if (arr[leftPos] > arr[i]) { swap(leftPos, i); i = leftPos; }else if (arr[rightPos] > arr[i]) { swap(rightPos, i); i = rightPos; }else { break; } }else if (leftPos <= size) { if (arr[leftPos] > arr[i]) { swap(leftPos, i); i = leftPos; }else { break; } }else { break; } leftPos = i * 2; rightPos = i * 2 + 1; } } // 删除根元素，然后调整,size-- void removeMax(){ swap(1, size); size--; adjustUpToDown(1); } // 删除根元素，并设置为新元素, size没变 void removeMax(int val){ arr[1] = val; adjustUpToDown(1); } // 插入到最后然后开始调整 void insert(int val){ arr[size+1] = val; size ++; // 从最后位置开始往上调整 adjustDownToUp(size); } int getRootVal(){ return arr[1]; } void print(){ if(size>0) { System.out.print(arr[1]); for (int i = 2; i <= size; i++) { System.out.print(" " + arr[i]); } } } } public class Main { public static Scanner sc = new Scanner(System.in); public static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); public static long mod = (long)Math.pow(2,29); public static void main(String[] args) throws Exception { int n = sc.nextInt(); int k = sc.nextInt(); int[] arr = new int[n]; for(int i=0;i<n;i++){ int val = sc.nextInt(); arr[i] = val; } MyHeap myHeap = new MyHeap(k); for(int i=0;i<n;i++){ if(!myHeap.isFull()){ myHeap.insert(arr[i]); }else { if(arr[i] < myHeap.getRootVal()){ myHeap.removeMax(arr[i]); } } } myHeap.print(); System.out.println(); } // 大根堆，存储k个节点 // 大于根的忽略，小于根的 替换根，并更新堆 } /* 5 3 3 5 1 5 2 3 1 2 */
import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.*; public class Main { public static Scanner sc = new Scanner(System.in); public static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); public static long mod = (long)Math.pow(2,29); public static void main(String[] args) throws Exception { int n = sc.nextInt(); int k = sc.nextInt(); int[] arr = new int[n]; for(int i=0;i<n;i++){ int val = sc.nextInt(); arr[i] = val; } if(k >= n){ k = n; }else { bfprt(arr,0, n-1, k); } // print 结果 System.out.print(arr[0]); for(int i=1;i<k;i++){ System.out.print(" " + arr[i]); } System.out.println(); } static void bfprt(int[] arr, int left, int right, int k){ findMid(arr, left, right); int pos = partition(arr, left, right); if(pos != -1) { int leftCnt = pos - left; if(left == k || left + 1 == k){ return; }else if(leftCnt + 1 < k) { bfprt(arr, pos + 1, right, k - (leftCnt + 1)); }else { bfprt(arr, left, pos - 1, k); } } } // 快排一次 static int partition(int[] arr, int left, int right){ if(left > right){ return -1; } int i = left; int j = right; int pivot = arr[left]; while (i < j){ while (i < j && arr[j] >= pivot){ j --; } arr[i] = arr[j]; while (i < j && arr[i] < pivot){ i ++; } arr[j] = arr[i]; } arr[i] = pivot; return i; } static void findMid(int[] arr, int left,int right){ if(left >= right){ return; } int num = 5; // 每 5 个划分一次 int cnt = 0; // 记录划分的总此次 for(int i=left;i<=right;i+=5){ int k1 = i; int k2 = i + num - 1; if(k1 > right){ break; } if(k2 > right){ k2 = right; } int medianPos = sortAndGetMedian(arr, k1, k2); // 将中位数放到 数组的最前面 swap(arr, left + cnt, medianPos); cnt ++; } // 中位数的中位数 放到arr的最前面 int tmp = sortAndGetMedian(arr, left, left + cnt - 1); swap(arr, tmp, left); } static int sortAndGetMedian(int[] arr, int left, int right){ insertSort(arr, left, right); int numCnt = right - left + 1; if(numCnt % 2 == 0){ return left + numCnt / 2 - 1; }else { return left + numCnt / 2; } } static void insertSort(int[] arr, int left, int right){ for(int i=left+1;i<=right;i++){ // 前面部分依次比较 for(int j=i-1;j>=left;j--){ if(arr[j+1] < arr[j]){ // 交换，大数放后面去 swap(arr, j, j+1); }else { break; } } } } static void swap(int[] arr, int i, int j){ int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } } /* 5 3 3 5 1 5 2 3 1 2 12 2 72 6 57 88 60 42 83 73 48 85 1 100 12 12 72 6 57 88 60 42 83 73 48 85 1 100 */