import java.util.Scanner; import java.util.PriorityQueue; public class Main { public static void main( String[] args ) { Scanner sc = new Scanner( System.in ); while( sc.hasNext() ) { Scanner num = new Scanner( sc.nextLine() ); int k = sc.nextInt(); PriorityQueue<Integer> queue = new PriorityQueue<>( (Integer i1, Integer i2)->i1-i2 ); for( int i = 0; i < k; i ++ ) queue.offer( num.nextInt() ); while( num.hasNextInt() ) { int tmp = num.nextInt(); if( tmp > queue.peek() ) { queue.poll(); queue.offer( tmp ); } } System.out.println( queue.peek() ); } sc.close(); } }
import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] strArr = br.readLine().split(" "); int[] arr = new int[strArr.length]; for (int i = 0; i < arr.length; i++) arr[i] = Integer.parseInt(strArr[i]); int k = Integer.parseInt(br.readLine()); System.out.println(quickSelect(arr, 0, arr.length - 1, k - 1)); } private static int quickSelect(int[] arr, int left, int right, int k) { int p = partition(arr, left, right); // 划分元素已经到了倒数第k,直接返回 if(p == k) return arr[p]; else if (p < k) return quickSelect(arr, p + 1, right, k); else return quickSelect(arr, left, p - 1, k); } private static int partition(int[] arr, int left, int right) { int pivot = arr[left]; int p = left; for(int i = left + 1; i <= right; i++){ if(pivot < arr[i]){ p ++; swap(arr, p, i); } } swap(arr, left, p); return p; } private static void swap(int[] arr, int i, int j) { int cache = arr[i]; arr[i] = arr[j]; arr[j] = cache; } }
import java.lang.System; import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; import java.util.PriorityQueue; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] strArr = br.readLine().split(" "); int k = Integer.parseInt(br.readLine()); int[] arr = new int[strArr.length]; for(int i = 0; i < arr.length; i++) arr[i] = Integer.parseInt(strArr[i]); PriorityQueue<Integer> minHeap = new PriorityQueue<>(); for(int i = 0; i < arr.length; i++){ if(minHeap.size() < k){ minHeap.offer(arr[i]); // 容量还未到k,直接入堆 }else{ if(arr[i] > minHeap.peek()){ // 容量到达k,如果当前元素能干掉堆顶,就弹出堆顶,新元素入堆 minHeap.poll(); minHeap.offer(arr[i]); } } } System.out.println(minHeap.peek()); // 最终堆顶就是k个大元素中最小的,即第k大的元素 } }
#include <bits/stdc++.h> using namespace std; int main(){ int a[100], k, n=0; while(true){ scanf("%d", &a[n++]); if(getchar()=='\n') break; } scanf("%d", &k); for(int i=0;i<n-1;i++) for(int j=0;j<n-i-1;j++) if(a[j]<a[j+1]) swap(a[j], a[j+1]); printf("%d\n", a[k-1]); return 0; }
import java.util.*; import java.util.stream.Collectors; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int[] inArr = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::valueOf).toArray(); ArrayList<Integer> nums = new ArrayList<Integer>(); for (int num : inArr) { nums.add(num); } int k = sc.nextInt(); solve(nums, nums.size()-k+1); System.out.println(ans); } private static int ans = -1; private static void solve(ArrayList<Integer> arr, int k) { ArrayList<Integer> left = new ArrayList<>(); ArrayList<Integer> right = new ArrayList<>(); int flagNum = arr.get(0); for (int i=1; i!=arr.size(); i++) { int cur = arr.get(i); if (arr.get(i) <= flagNum) { left.add(cur); } else { right.add(cur); } } if (left.size() == k-1) { ans = flagNum; return; } if (left.size() < k) { solve(right, k-left.size()-1); } else if (left.size() >= k) { solve(left, k); } } }
import java.util.Scanner; /** * 类似与求第k小的问题 * 求第k大相当于求第n-k+1小,n为数组长度 * * 著名的BFPRT算法可保证在线性时间内得到结果。 * https://blog.csdn.net/qq_32767041/article/details/86099117 * * 这里使用快速选择算法,这是一种基于快速排序的算法, * 在实现上比BFPRT更简单。 * https://blog.csdn.net/qq_32767041/article/details/86300744 * * @author wylu */ public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); while (scanner.hasNext()) { String[] strs = scanner.nextLine().split(" "); int[] arr = new int[strs.length]; for (int i = 0; i < arr.length; i++) { arr[i] = Integer.valueOf(strs[i]); } int k = scanner.nextInt(); System.out.println(arr[quickSelect(arr, arr.length - k + 1)]); } } /** * 查找第k小元素 * @param arr 无序数组 * @param k 目标第k小 * @return 成功:返回第k小元素的索引 * 失败:返回-1 */ public static int quickSelect(int[] arr, int k) { int left = 0, right = arr.length - 1, idx; while (left <= right) { idx = partition(arr, left, right); if ((k - 1) == idx) return idx; else if ((k - 1) > idx) left = idx + 1; else right = idx - 1; } return -1; } /** * 对给定的数组区间进行划分 * @param arr 数组 * @param left 区间下限,包含arr[left] * @param right 区间上限,包含arr[right] * @return 返回划分后,划分基准的索引 */ private static int partition(int[] arr, int left, int right) { int j = left - 1; for (int i = left; i < right; i++) { if (arr[i] <= arr[right]) swap(arr, i, ++j); } swap(arr, ++j, right); return j; } private static void swap(int[] arr, int i, int j) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } }
#include <iostream> #include <queue> #include <vector> using namespace std; int top_k(vector<int> & nums){ priority_queue<int,vector<int>,greater<int>> pq; int i,j; for(i=0;i<nums.back();++i) pq.push(nums[i]); for(j=i;j<nums.size()-1;++j) if(nums[j]>pq.top()){ pq.pop(); pq.push(nums[j]); } return pq.top(); } int main(void){ vector<int> nums; int num; while(cin>>num){ nums.push_back(num); } cout<<top_k(nums)<<endl; }
#include <cstdio> #include <cstdlib> #include <ctime> #include <cmath> #define N 100010 int randPatition(int arr[],int left, int right) { int r = round(rand() * 1.0 / RAND_MAX * (right-left) + left); int t=arr[r]; arr[r]=arr[left]; arr[left]=t; int s=left; int e=right; while(s<e){ while(s<e && arr[e]>t){ e--; } arr[s]=arr[e]; while(s<e && arr[s]<=t){ s++; } arr[e]=arr[s]; } arr[s]=t; return s; } int randSelect(int arr[],int left,int right,int k){ if(left>=right){ if(k==1){ return arr[left]; }else{ return 0;//not found } } int p = randPatition(arr,left,right); int m = right - p + 1; if(m==k){ return arr[p]; }else if(m>k){ return randSelect(arr,p+1,right,k); }else{ return randSelect(arr,left,p-1,k-m); } } int main(){ srand(unsigned(time(NULL))); int arr[N]; int k; int n=0; while(~scanf("%d",&k)){ arr[n++]=k; } n--; int res = randSelect(arr,0,n-1,k); printf("%d\n",res); return 0; }
import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); String[] str = sc.nextLine().split(" "); int k = sc.nextInt(); int len = str.length; int[] arr = new int[len]; for (int i = 0; i < len; i++) { arr[i] = Integer.parseInt(str[i]); } PriorityQueue<Integer> minHeap = new PriorityQueue<>(k); for (int x : arr) { if (minHeap.size() < k) { minHeap.offer(x); } else { if (minHeap.peek() < x) { minHeap.poll(); minHeap.offer(x); } } } System.out.println(minHeap.peek()); } }
#include <iostream> #include <vector> #include <queue> #include <cstdio> using namespace std; int main(){ priority_queue<int,vector<int>,greater<int>> pq; // 小根堆 vector<int> arr; int ele; while(cin >> ele){ arr.push_back(ele); if(getchar() == '\n') break; } int k ; cin >> k; for(int i = 0;i < arr.size();i++){ pq.push(arr[i]); if(pq.size() > k) pq.pop(); } printf("%d",pq.top()); }小根堆
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Main{ public static void main(String[] args) throws IOException { BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); String[] S =bf.readLine().split(" "); int[] a = new int[S.length]; for(int i = 0;i < S.length;i++){ a[i] = Integer.valueOf(S[i]); } int k = Integer.parseInt(bf.readLine()); Arrays.sort(a); System.out.println(a[a.length-k]); } }
#include<iostream> #include<bits/stdc++.h> using namespace std; vector<int>nums; int main(){ int temp; while(cin>>temp) nums.push_back(temp); int k = nums.back(); nums.pop_back();//这里为什么将最后一个元素删除? int size = nums.size(); if(k>=size){ cout<<"输入的k错误"<<endl; return -1; }else{ sort(nums.begin(),nums.end()); cout<<nums[size - k]<<endl; } return 0; }
import java.util.Scanner; import java.util.Arrays; public class Main { public static void main(String[] args){ Scanner in = new Scanner(System.in); int[] arr = Arrays.stream(in.nextLine().split(" ")).mapToInt(Integer::valueOf).toArray(); System.out.print(sort(arr, 0, arr.length - 1,arr.length - in.nextInt())); } public static int sort(int[] array, int left, int right,int k){ int key = array[left]; int i = left, j = right; while (i < j){ while (key <= array[j] && i < j){ j--; } while (key >= array[i] && i < j){ i++; } if (i < j){ int temp = array[i]; array[i] = array[j]; array[j] = temp; } } array[left] = array[i]; array[i] = key; if(k == i) return array[i]; if(k > i) return sort(array, i + 1, right,k); else return sort(array, left, i - 1,k); } }这是最快解法吧!
我用vs试了一下,以下代码是可以的,但是在这上面不成功。 #include <iostream> using namespace std; void BubbleSort(int arr[], int n) { for (int i = 0; i < n - 1; i++) { for (int j = 0; j < n - i - 1; j++) { if (arr[j] < arr[j + 1]) { int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } } int main() { int a, x; int s[100]; for (int i = 0; i < 100; i++) { cin >> s[i]; if (cin.get() == '\n') break; } cin >> x; BubbleSort(s, 100); a = s[x - 1]; cout << a << endl; system("pause"); }
#include<bits/stdc++.h> using namespace std; int main(){ priority_queue<int, vector<int>, greater<int>> pq; vector<int> nums; int t; while(cin >> t){ nums.push_back(t); } int k = nums[nums.size()-1]; for(int i = 0; i < nums.size()-1; i++){ if(pq.size() < k){ pq.push(nums[i]); }else{ if(nums[i] > pq.top()){ pq.pop(); pq.push(nums[i]); } } } cout << pq.top() << endl; }
import java.util.*; public class Main{ public static void main(String[] args){ Scanner sc=new Scanner(System.in); List<Integer> list=new ArrayList<>(); while(sc.hasNext()){ list.add(sc.nextInt()); } int n=list.get(list.size()-1); list.remove(list.size()-1); list.sort(new Comparator<Integer>(){ public int compare(Integer i2,Integer i1){ return i1-i2; } }); System.out.println(list.get(n-1)); } }