晋级人数

n, x = map(int, input().split())
score = [int(x) for x in input().split()]
# print(score)
score = sorted(score, reverse=True)
# print(score)
x_score = score[x-1]
num = 0

for i in range(len(score)):
	if score[i] >= x_score and score[i] != 0:
		num += 1

print(num)

• 语言：Java

题解

计划该环节晋级人数为x人，则将所有人的分数从高到低排序，所有分数大于等于第x个人的分数且得分不为0的人都可以晋级,可能存在重复的分数情况；

例如

n=8 x=5
arr：0 1 1 1 2 3 4 5

排名第五的分数为arr[3]= 1；但是arr[0]和arr[1] 分数也为1；故也算晋级的人；

1. 将得分数组arr从小到大排序；
2. 排名第五的人分数为base=arr[n-x];
3. 遍历数组arr：
   • 如果遍历到的分数为0,跳过；
   • 直到遍历到分数=base,则能晋级的人数为n-i

代码

import java.io.*;
import java.util.Arrays;
public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s = br.readLine().trim().split(" ");
        int n = Integer.parseInt(s[0]);
        int x = Integer.parseInt(s[1]);

        int[] arr = new int[n];
        s = br.readLine().trim().split(" ");
        for(int i = 0; i < n; i++){
            arr[i] = Integer.parseInt(s[i]);
        }
        int res = 0;
        int len = arr.length;
        Arrays.sort(arr);
        int base = arr[n - x];
        for(int i = 0; i < n; i++){
            if(arr[i] == 0) continue;
            else if(arr[i] == base) {
                res =n - i;
                break;
            }
        }
        System.out.println(res);
    }
}

复杂度

• 时间复杂度：O(N)

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main() {
    int n, x;
    cin>>n>>x;
    int res = x;
    vector<int> nums(n, -1);
    for(int i = 0; i < n; i++) cin>>nums[i];
    sort(nums.rbegin(), nums.rend());
    int index = x - 1;
    if(nums[0] == 0) res = 0;
    else{
        if(nums[index] != 0) {
            for(int i = index + 1; i < n; i++) {
                if(nums[i] == nums[i - 1]) res++;
                else break;
            }
        }else {
            while(index >= 0 && nums[index] == 0){
                index--;
                res--;
            } 
        }
    } 
    cout<<res;
    return 0;
}

n, x = map(int, input().split())
score = [int(x) for x in input().split()]
score = sorted(score)
score.reverse()
tem = 0
aim = score[x-1]
new = []
for i in score:
  if i >= aim and i != 0:
    new.append(i)

print(len(new))

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String s1 = in.nextLine();
        String s2 = in.nextLine();
        int n = Integer.parseInt(s1.split(" ")[0]);
        int x = Integer.parseInt(s1.split(" ")[1]);
        int[] scores = new int[n];
        String[] str = s2.split(" ");
        for (int i = 0; i < n; i++) {
            scores[i] = Integer.parseInt(str[i]);
        }
        Arrays.sort(scores);
        int res = x;
        int line = scores[n - x];
        for (int i = n - x - 1; i >= 0; i--) {
            if (scores[i] >= line) {
                res++;
            }else {
                break;
            }
        }
        System.out.println(res);
    }
}

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;


public class Test02 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str = br.readLine().split(" ");
        int n = Integer.parseInt(str[0]);
        int x = Integer.parseInt(str[1]);
        int[]ans = new int[n];
        String[] str1 = br.readLine().split(" ");
        for(int i=0;i<n;i++){
            ans[i] = Integer.parseInt(str1[i]);
        }
        Arrays.sort(ans);
        int i=0;
        for(i=n-x-1;i<n;i++){
            if(ans[i]!=0)break;
        }
        if(i<n){
            for(;ans[i]!=0&&i-1>=0;i--) {
                if (ans[i] != ans[i - 1]) break;
            }
        }
        System.out.println(n-i);

    }
}

简简单单排个序

import java.util.*;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] arr = br.readLine().split(" ");
        int n = Integer.valueOf(arr[0]), x = Integer.valueOf(arr[1]);
        Integer[] scores = Arrays.stream(br.readLine().split(" ")).map(Integer::valueOf).filter(v -> v > 0).toArray(Integer[]::new);
        Arrays.sort(scores, (o1, o2) -> o2 - o1);
        if (scores.length <= x) {
            bw.write(String.valueOf(scores.length));
        } else {
            int i = x;
            while (i < scores.length && scores[i].equals(scores[x - 1])) i++;
            bw.write(String.valueOf(i));
        }
        bw.flush();


    }
}

这道题其实就是求TopK问题的，只不过包装了一下，本质是获取到输入后，求解数组集合中第k大的数字是什么。那么我们有三种方法：

• 直接调用API排序，时间复杂度O(NlogN)
• 使用优先队列，维护一个最小堆，存放前k大元素，堆顶就是我们的第k大元素，时间复杂度O(NlogK)
• 使用快排的partition操作，每次找到一个排序的位置，然后判断是不是我们要找的那个，如果不是就缩小范围。时间复杂度O(N)

import java.util.Scanner;
import java.util.Arrays;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int x = in.nextInt();
        Integer[] a = new Integer[n];
        for(int i = 0; i < n; i++) {
            a[i] = in.nextInt();
        }
        Arrays.sort(a, (o1, o2) -> o2-o1);
        int ans = 0;
        for(int i = 0; i < n; i++) {
            if(a[i] != 0 && a[i] >= a[x-1]) {
                ans++;
            }
        }
        System.out.println(ans);
    }
}