2021-12-02 506. 相对名次

排序应用的一个思路：
首先用一个数组(tmp)储存之前的数组的值，对原数组进行排序，接着用hashmap储存(key=排序后数组的value,排序后数组的location)，接着用tmp数组一个一个遍历取出hashmap的value,并转换城题目需要的形式。计算复杂度3*O(n)
java版本：

class Solution {
    public String[] findRelativeRanks(int[] score) {
        // 有点像排序
        // 不改变location 记录标号
        int n=score.length;

        HashMap<Integer,Integer> hashmap=new HashMap<>();
        
      int[] score_tmp=new int[n];
         for(int i=0;i<n;i++){    
         score_tmp[i]=score[i];
        }
     // 运用排序算法 构造另一个数组
        score=HilerSortGet(score,n,n/2);
        //   Arrays.sort(score);
        for(int i=0;i<n;i++){
          hashmap.put(score[i],n-i-1);
        }
    
        String[] res=new String[n];

          for(int i=0;i<n;i++){
               System.out.println(score_tmp[i]);
             res[i]=GetScores(hashmap.get(score_tmp[i]));
        }
        return res;

    }
    public String GetScores(int i){
   String[] score_str={"Gold Medal","Silver Medal","Bronze Medal"};
   if (i<3){
       return score_str[i];
   }
   return Integer.toString(i+1);
    }
      public int[]  HilerSortGet(int[] arr,int n,int dk){
        while(dk>=1){
            for(int i=dk;i<n;i++){
                if(arr[i]<arr[i-dk]){
                    int j=i-dk;
                    int x=arr[i];
                    arr[i]=arr[i-dk];
                    while(j>=0 && x<arr[j]){
                        arr[j+dk]=arr[j];
                        j-=dk;
                    }
                    arr[j+dk]=x;
                }
            }
            dk=dk/2;
        }
        return arr;
    }
}