查找第K大的元素

我来给出这类题的通用解法，也就是求无序数组的第K大(或第K小)的问题，下面给出两种AC了的方法

import java.util.PriorityQueue;
import java.util.Scanner;
import static java.lang.Integer.parseInt;
import static java.lang.System.in;

public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(in);
        String[] str = sc.nextLine().replace("[", "").replace("]", "").split(",");
        int[] data = new int[str.length];
        for (int i = 0; i < data.length; i++) {
            data[i] = parseInt(str[i]);
        }
        System.out.println(findKthNum(data, 3));
        System.out.println(findKthNum1(data, 3));
    }
//方法1，基于快排思想的partion划分，时间复杂度O(n)，空间复杂度O(1)
    public static int findKthNum(int[] data, int k) {
        int begin = 0, end = data.length - 1;
        int pos = 0;
        while (begin <= end) {
            pos = partion(data, begin, end);
            if (pos == k - 1) {
                return data[pos];
            } else if (pos > k - 1) {
                end = pos - 1;
            } else {
                begin = pos + 1;
            }
        }
        return -1;
    }

    private static int partion(int[] data, int begin, int end) {
        int temp = data[begin];
        while (begin < end) {
            while (begin < end && data[end] <= temp) {
                end--;
            }
            swap(data, begin, end);
            while (begin < end && data[begin] > temp) {
                begin++;
            }
            swap(data, begin, end);
        }
        return begin;
    }

    public static void swap(int[] arr, int i, int j) {
        if (arr == null || i >= arr.length || j >= arr.length || i < 0 || j < 0) {
            return;
        }
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    //方法2，建小顶堆，时间复杂度O(n*logk),空间复杂度O(k)
    public static int findKthNum1(int data[], int k) {
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        for (int item : data) {
            if (heap.size() < k) {
                heap.add(item);
            } else if (item > heap.peek()) {
                heap.poll();
                heap.add(item);
            }
        }
        return heap.poll();
    }
}

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
 
bool compare(const int &a,const int &b)
{
    return a>b;
}
 
int main()
{
    int num;
    vector<int> v;
    while(getchar()!=']')
    {
        cin>>num;
        v.push_back(num);
    }
    sort(v.begin(),v.end(),compare);
    cout<<v[2];
}

#include<bits/stdc++.h> 
using namespace std; 
int main()
{
    vector<int> a;
    string s;
    cin >> s;
    int cur, sign = 1;
    for (int i = 1; i < s.length(); i++)
    {
        if (!isdigit(s[i]) && s[i] != '-')
        {
            a.push_back(cur * sign);
            cur = 0;
            sign = 1;
        }
        else if (isdigit(s[i]))
            cur = cur * 10 + s[i] - '0';
        else
            sign = -1;
    }
    sort(a.begin(),a.end());
    cout<<a[a.size()-3]<<endl;
    return 0;
}

import java.util.Scanner;
import java.util.Arrays;
public class Main{
    public static void main(String[] args){
        Scanner input=new Scanner(System.in);
        String[] str=input.nextLine().replace("[","").replace("]","").split(",");
        int strInt[]=new int[str.length];
        for(int i=0;i<str.length;i++){
            strInt[i]=Integer.parseInt(str[i]);
        }
        Arrays.sort(strInt);
        System.out.println(strInt[strInt.length-3]);
    }
}

print(sorted(map(int,eval(input())))[-3])

#include <bits/stdc++.h>
using namespace std;

int main(){
    vector<int> a;
    string s;
    cin>>s;
    stringstream ss(s);
    int x;
    char c;
    while(ss>>c){
        if(c==']')
            break;
        ss>>x;
        a.push_back(x);
    }
    priority_queue<int, vector<int>, greater<int>> q;
    for(int i=0;i<a.size();i++){
        if(q.size()<3)
            q.push(a[i]);
        else{
            if(a[i]>q.top()){
                q.pop();
                q.push(a[i]);
            }
        }
    }
    cout<<q.top()<<endl;
    return 0;
}

冒泡思想pop三趟就行。
不知道今天牛客怎么了，后台一直出错，自己在本地都可以AC。
#include<iostream>
#include<vector>
using namespace std;

int main()
{
    vector<int> input;
    int tmp;
    while(cin>>tmp)
    {
        input.push_back(tmp);
        if(cin.get()=='\n')
            break;
    }
    int n=input.size();
    for(int i=0;i<3;i++)
    {
        for(int j=0;j<n-i-1;j++)
        {
            if(input[j]>input[j+1])
            {
                tmp=input[j+1];
                input[j+1]=input[j];
                input[j]=tmp;
            }
        }
    }
    cout<<input[n-3];
}

#include <bits/stdc++.h>
using namespace std;
int mypartition(vector<int> &arr,int start,int end,int k){
    int left=start,right=end;
    int p=arr[left];
    if(start<end){
        while(left<right){
            while(left<right&&arr[right]<=p)
                right--;
            arr[left]=arr[right];
            while(left<right&&arr[left]>=p)
                left++;
            arr[right]=arr[left];
        }
        arr[left]=p;
        if(left==k)
            return arr[k];
        else if(left>k)
            return mypartition(arr,start,left-1,k);
        else
            return mypartition(arr,left+1,end,k);
    }
}
int main(){
    vector<int> arr(1,0);
    cin.ignore();
    while(1){
        int t;
        cin>>t;
        arr.push_back(t);
        if(cin.get()==']')
            break;
    }
    int ans=mypartition(arr,1,arr.size()-1,3);
    cout<<ans;
    return 0;
}

""""
求第k大值
"""

if __name__ == "__main__":
    a = eval(input().strip())
    print(sorted(a)[-3])

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <sstream>

using namespace std;

int main() {
    string input,tmp;
    while (cin>>input) {
        vector<int> array;
        input.erase(input.end() - 1);
        input.erase(input.begin());
        stringstream inputline(input);
        while(getline(inputline, tmp, ',')) {
            auto v = stoi(tmp);
            array.push_back(v);
        }
        sort(array.begin(),array.end());
        cout<<array[array.size() - 3]<<endl;
    }
    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String str = scanner.next();
        String[] strNumber = str.substring(1, str.length() - 1).split(",");
        int[] number = new int[strNumber.length];
        for (int i = 0; i < strNumber.length; i++) {
            number[i] = Integer.parseInt(strNumber[i]);
        }
        Arrays.sort(number);
        System.out.println(number[number.length -3]);
    }
}

#include<iostream>
#include<cstdio>
#include<limits.h>
using namespace std;

int main()
{
    int x=INT_MIN,y=INT_MIN,z=INT_MIN;//x第一大，y第二大，z第三大
    int k;
    while(getchar()!=']')
    {
        cin>>k;
        if(k>=x)
        {
            z=y;    y=x;    x=k;
        }
        else if(k>=y)
        {
            z=y;    y=k;
        }
        else if(k>=z)
        {
            z=k;
        }
        else
            continue;
    }
    cout<<z<<endl;
    return 0;
}

第一次使用ACM模式，真难受

我就偷个懒，直接解析字符串数字，不要数组了

import java.util.Scanner;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.io.PrintWriter;
import java.io.OutputStreamWriter;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
     public static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
     public static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));

     public static void main(String[] args) throws Exception {

        String s = reader.readLine();
        if( s!=null) {
            out.println(parseIntArray(s));
        }
        out.flush();
    }

    public static int parseIntArray(String s) {
        int mx1 = Integer.MIN_VALUE;
        int mx2 = Integer.MIN_VALUE;
        int mx3 = Integer.MIN_VALUE;
        int base = 0;
        int deep = 0;
        int isNeg = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '\n' || c == '\t' || c == '\f' || c == '\r' || c == ' ')
                continue;
            switch (c) {
            case '[':
                base = 0; // 初始化
                deep++;
                break;
            case ']':
                deep--;
                if (deep == 0) {
                    if (isNeg > 0) {
                        base *= -1;
                        isNeg--;
                    }
                    if ( mx1 < base) {
                        mx3 = mx2;
                        mx2 = mx1;
                        mx1 = base;
                    } else if ( mx2 < base ) {
                        mx3 = mx2;
                        mx2 = base;
                    } else if ( mx3 < base ) {
                        mx3 = base;
                    }
                }
                break;
            case '-':
                isNeg++;
                break;
            case ',':
                if (isNeg > 0) {
                    base *= -1;
                    isNeg--;
                }
                // arr[size++] = base;
                if ( mx1 < base) {
                    mx3 = mx2;
                    mx2 = mx1;
                    mx1 = base;
                } else if ( mx2 < base ) {
                    mx3 = mx2;
                    mx2 = base;
                } else if ( mx3 < base ) {
                    mx3 = base;
                }
                base = 0;
                break;
            default:
                if( c >= '0' && c <= '9') {
                    base = base * 10 + c - '0';
                }

                break;
            }
        }
        return mx3;
    }
}