leetcode506. Relative Ranks

题目要求

Given scores ofNathletes, find their relative ranks and the people with the top three highest scores, who will be awarded medals: "Gold Medal", "Silver Medal" and "Bronze Medal".

Example 1:

Input: [5, 4, 3, 2, 1] Output: ["Gold Medal", "Silver Medal", "Bronze Medal", "4", "5"] Explanation: The first three athletes got the top three highest scores, so they got "Gold Medal", "Silver Medal" and "Bronze Medal". For the left two athletes, you just need to output their relative ranks according to their scores.

Note:

  1. N is a positive integer and won't exceed 10,000.
  2. All the scores of athletes are guaranteed to be unique.

现有N名运动员的成绩,用一个正整数数组来表示,已知该正整数数组中的成绩均唯一。要求用一个String数组返回对应下标上运动员的相对排名,其中前三名分别标记为"Gold Medal", "Silver Medal"和"Bronze Medal",其它则用数字表示排名。

思路和代码

这题直观的来看可以用排序得出运动员从高到低的得分,但是这样就丢失了分数原来的下标。因此,假如我们可以将0-n这n个数字进行排序,排序的标准为对应的运动员的成绩。再根据下标将排序结果依次写会。

过程如下:

假如一组运动员成绩为[1,3,2,5,4]
对应的下标为[0,1,2,3,4]
则对第二个数组按照其对应的成绩由低到高的排序结果为[3,4,1,2,0]
再根据这个结果依次将结果写入String数组中,
result[3]="Gold Medal", result[4]="Silver Medal", result[1]="Bronze Medal" result[2]="4" result[0]="5"

代码如下:

   public String[] findRelativeRanks(int[] nums) {
       if (nums.length == 0) return new String[0];
       Integer[] indexes = Stream.iterate(0, i -> i+1).limit(nums.length).sorted(new Comparator<Integer>() {
           @Override
           public int compare(Integer o1, Integer o2) {
               return nums[o2] - nums[o1];
           }
       }).toArray(Integer[]::new);

       String[] result = new String[nums.length];
       for (int i = 0 ; i<indexes.length ; i++) {
           if (i == 0) {
               result[indexes[i]] = "Gold Medal";
           } else if (i == 1) {
               result[indexes[i]] = "Silver Medal";
           } else if (i == 2) {
               result[indexes[i]] = "Bronze Medal";
           } else {
               result[indexes[i]] = String.valueOf(i+1);
           }
       }
       return result;
   }

这里使用了JAVA内置的排序,也可以使用桶排序来降低时间复杂度。

    public String[] findRelativeRanks(int[] nums) {
       if (nums.length == 0) return new String[0];
       int maxValue = IntStream.of(nums).max().getAsInt();

       int[] buckets = new int[maxValue+1];
       for (int i = 0 ; i<nums.length ; i++) {
           buckets[nums[i]] = i+1;
       }

       int place = 1;
       String[] result = new String[nums.length];
       for (int i = buckets.length-1 ; i>=0 ; i--) {
           if (buckets[i] == 0) continue;
           if (place <= 3) {
               if (place == 1) {
                   result[buckets[i]-1] = "Gold Medal";
               } else if (place == 2) {
                   result[buckets[i]-1] = "Silver Medal";
               } else {
                   result[buckets[i]-1] = "Bronze Medal";
               }
           } else {
               result[buckets[i]-1] = String.valueOf(place);
           }
           place++;
       }
       return result;
   }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • leetcode491. Increasing Subsequences

    这里采用深度优先的思路进行解决。先将数组按照从小到大排序,再从左往右遍历数组,每个数字有两种可能,分别是选中到子数组,或者不选中。将所有的结果收纳即可获得最终的...

    眯眯眼的猫头鹰
  • leetcode542. 01 Matrix

    Given a matrix consists of 0 and 1, find the distance of the nearest 0 for each ...

    眯眯眼的猫头鹰
  • leetcode417. Pacific Atlantic Water Flow

    假设左上角的所有周围面积为太平洋,右下角的所有面积为大西洋。现在使用数组来表示一大片水域,其中数组的每一个位置上的元素代表某一个小水域的高度。假定水只能从高出流...

    眯眯眼的猫头鹰
  • 如何利用好KE02 内部的EEPROM

    最近有几个项目用的是NXP的 KE02片子这个芯片内部自带256字节的EEPROM,可以用来存一些参数,和密码,但是操作的时候要注意,EEPROM的地址是0x1...

    用户1605515
  • Flink应用程序结构开发介绍

    Flink程序遵循一定的编程模式。DataStream API 和 DataSet API 基本具有相同的程序结构。以下为一个流式程序的示例代码来对文本文件进行...

    chaplinthink
  • 使用bee自动生成api文档

    beego中的bee工具可以方便的自动生成api文档,基于数据库字段,自动生成golang版基于beego的crud代码,方法如下: 1、进入到gopath目录...

    用户1141560
  • AkShare-股票数据-千股千评

    熟悉东方财富的小伙伴一定听过东方财富的股吧评论数据,无论是学术论文还是业界的金工报告都有提及相关内容,本次更新根据股吧浏览、自选股添等数据统计得出,关注指数越高...

    AkShare
  • Python 对数字的千分位处理

    py3study
  • 动态神经网络工具包Dynet

    作者|Murat 译者|陈亮芬 编辑|Emily 基于诸如 TensorFlow 等几种流行工具包的编程模型使用的是静态声明方法,这些工具包将网络架构的声明和执...

    企鹅号小编
  • Spring Cloud Sleuth进阶实战

    为什么需要Spring Cloud Sleuth 微服务架构是一个分布式架构,它按业务划分服务单元,一个分布式系统往往有很多个服务单元。由于服务单元数量众多,业...

    方志朋

扫码关注云+社区

领取腾讯云代金券