[编程题]晋级人数(美团)

• 语言：Java

题目

团是某综艺节目的策划，他为某个游戏环节设计了一种晋级规则，已知在这个游戏环节中每个人最后都会得到一个分数score_i，显而易见的是，游戏很有可能出现同分的情况，小团计划该环节晋级人数为x人，则将所有人的分数从高到低排序，所有分数大于等于第x个人的分数且得分不为0的人都可以晋级。

请你求出本环节的实际晋级人数。显然这个数字可能是0，如果所有人的得分都是0，则没有人满足晋级条件。

输入描述:

输入第一行包含两个正整数n和x，分别表示参加本环节的人数，和小团指定的x。
输入第二行包含n个整数，每个整数表示一位选手的得分。

输出描述:

输出仅包含一个整数，表示实际晋级人数。

示例1
输入

5 4
0 0 2 3 4

输出

3

题解

计划该环节晋级人数为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. 排名第x的人分数为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)
• 空间复杂度：O(1)