This is the seventh day of my participation in the First Challenge 2022. For details: First Challenge 2022.

📢 preface

🚀 Algorithm 🚀
  • 🌲 punch in an algorithm every day, which is not only a learning process, but also a sharing process 😜
  • 🌲 tip: the programming languages used in this column are C# and Java
  • 🌲 to maintain a state of learning every day, let us work together to become a god of algorithms 🧐!
  • 🌲 today is the force button algorithm continued to punch the card 67 days 🎈!
🚀 Algorithm 🚀

🌲 Relative ranking

Give the results of N athletes, find out their relative positions and award the MEDALS corresponding to the top three. The top three athletes will be awarded the “Gold Medal”, “Silver Medal” and “Bronze Medal” respectively.

(Note: The higher the score, the higher the ranking.)

Example 1:

Input:5.4.3.2.1] output: ["Gold Medal"."Silver Medal"."Bronze Medal"."4"."5"The top three athletes will be awarded gold, silver and bronze MEDALS respectively. ["Gold Medal"."Silver Medal" and "Bronze Medal"For the remaining two athletes, we only need to calculate their relative positions according to their results.Copy the code

Tip:

  • N is a positive integer and does not exceed 10000.
  • All athletes have different results.

🌻 c # method

Save the original index first, then sort

Code:

public class Solution {
class Pair {
    public int idx;
    public int rank;
}
string[] medalStr = { ""."Gold Medal"."Silver Medal"."Bronze Medal" };
string GetRankStr(int rank) {
    if (rank > 3) return rank.ToString();
    else return medalStr[rank];
}
public string[] FindRelativeRanks(int[] nums) {
    int n = nums.Length;
    Pair[] ps = new Pair[n];
    for (int i = 0; i < n; ++i) 
        ps[i] = new Pair() { idx = i, rank = nums[i] };
    Array.Sort(ps, (a, b) => b.rank - a.rank);
    string[] ans = new string[n];
    for (int rank = 0; rank < n; )
        ans[ps[rank].idx] = GetRankStr(++rank);
    returnans; }}Copy the code

The execution result

By execution time:88Ms, beat out all Java commits22.50% user memory consumption:36.4MB, beat out all Java commits12.50% of the userCopy the code

🌻Java method: sort

The idea of parsing first sort, using hash solution

Code:

class Solution {
    public String[] findRelativeRanks(int[] score) {

        int len = score.length;
        String[] rank = new String[len];
        // Let's do some sorting
        int[] x = score.clone();
        Arrays.sort(score);
// System.out.println(Arrays.toString(score));

        // Hash the ranking
        HashMap<Integer, String> map = new HashMap<>();
        if (len > 3) {
            for (int i = len - 4; i >= 0; --i) {
                map.put(score[i], len - i + "");
            }
            map.put(score[len-1]."Gold Medal");
            map.put(score[len-2]."Silver Medal");
            map.put(score[len-3]."Bronze Medal");
        } else {
            if( len == 1) {
                map.put(score[0]."Gold Medal");
            } else if ( len == 2) {
                map.put(score[0]."Silver Medal");
                map.put(score[1]."Gold Medal");
            } else {
                 map.put(score[0]."Bronze Medal");
                 map.put(score[1]."Silver Medal");
                 map.put(score[2]."Gold Medal"); }}for (int i = 0; i < len; i++) {
            rank[i] = map.get(x[i]);
        }
        returnrank; }}Copy the code

The execution result

By execution time:11Ms, beat out all Java commits48.26% user memory consumption:39.2MB, beat out all Java commits78.05% of the userCopy the code

💬 summary

  • Today is the sixty-seventh day of force buckle algorithm title punch!
  • The article USES theC# andJavaTwo programming languages to solve the problem
  • Some methods are also written by the god of reference force buckle, and they are also shared while learning, thanks again to the algorithm masters
  • That’s the end of today’s algorithm sharing, see you tomorrow!