ວິທີແກ້ໄຂບັນຫາ Leetcode


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ ກູໂກ
ຮຽງລໍາດັບ

ບັນຫາ Relative Ranks Leetcode Solution ຂໍໃຫ້ພວກເຮົາກັບຄືນຮູບແບບ vector ຫລືແຖວຂອງສາຍທີ່ເປັນຕົວແທນໃຫ້ແກ່ລະດັບພີ່ນ້ອງ. ພວກເຮົາສະ ໜອງ ໃຫ້ກັບ array ທີ່ເປັນຕົວແທນໃຫ້ຄະແນນທີ່ໄດ້ຮັບໂດຍນັກກິລາ. ຫຼັງຈາກນັ້ນ, ພວກເຮົາໃຊ້ຂອບຄະແນນທີ່ມອບໃຫ້ເພື່ອຈັດລຽງ ລຳ ດັບ. ມີການປ່ຽນແປງເລັກ ໜ້ອຍ ສຳ ລັບຜູ້ສະ ໝັກ 3 ຄົນທີ່ສູງສຸດ. ແທນທີ່ຈະ, ມອບ ໝາຍ ເລກງ່າຍໆໃຫ້ພວກເຂົາ 1, 2, ຫລື 3. ພວກເຮົາ ຈຳ ເປັນຕ້ອງມອບຫລຽນ ຄຳ, ເງິນ, ແລະຫລຽນທອງ. ນອກ ເໜືອ ຈາກຜູ້ສະ ໝັກ 3 ຄົນສູງສຸດ, ພວກເຮົາສາມາດມອບ ໝາຍ ເລກງ່າຍໆໃຫ້ພວກເຂົາຈາກ 4 ເຖິງ n. ຂໍໃຫ້ພິຈາລະນາບາງຕົວຢ່າງ.

ວິທີແກ້ໄຂບັນຫາ Leetcode

[1, 2, 3]
["Bronze Medal", "Silver Medal", "Gold Medal"]

ຄໍາອະທິບາຍ: ນັບຕັ້ງແຕ່ຕາຕະລາງທີ່ມອບໃຫ້ເປັນຕົວແທນໃຫ້ຄະແນນຂອງນັກກິລາ. ນັກກິລາທີ່ມີຄະແນນສູງສຸດຈະໄດ້ຮັບຫຼຽນ ຄຳ ແລະອື່ນໆ. ດັ່ງນັ້ນພວກເຮົາໄດ້ມອບຫຼຽນ ຄຳ ໃຫ້ນັກກິລາດ້ວຍຄະແນນ 3, ຫຼຽນເງິນໃຫ້ນັກກິລາດ້ວຍຄະແນນ 2, ແລະຫຼຽນທອງໃຫ້ນັກກິລາດ້ວຍຄະແນນ 1.

[5, 4, 3, 2, 1]
["Gold Medal", "Silver Medal", "Bronze Medal", "4", "5"]

ຄຳ ອະທິບາຍ: ເນື່ອງຈາກຜູ້ສະ ໝັກ 3 ຄົນທີ່ໄດ້ຮັບລາງວັນສູງສຸດແລະຜູ້ສະ ໝັກ ທີ່ເຫຼືອແມ່ນໄດ້ຮັບ ຕຳ ແໜ່ງ. ດັ່ງນັ້ນພວກເຮົາໄດ້ມອບ ໝາຍ ໃຫ້ແກ່ຜູ້ທີ່ໄດ້ຮັບລາງວັນສູງສຸດ 3 ຄົນ, ແລະໄດ້ຈັດອັນດັບທີ 4, ແລະ 5 ໃຫ້ແກ່ຜູ້ສະ ໝັກ ທີ່ສອດຄ້ອງກັນ.

ວິທີການ

ບັນຫາ Relative Ranks Leetcode Solution ຂໍໃຫ້ພວກເຮົາມອບຫລຽນ ຄຳ ໃຫ້ແກ່ຜູ້ສະ ໝັກ 3 ຄົນທີ່ສູງສຸດແລະມອບ ໝາຍ ຕຳ ແໜ່ງ ໃຫ້ຜູ້ສະ ໝັກ ທີ່ເຫລືອ. ສິ່ງທີ່ລຽບງ່າຍທີ່ສຸດທີ່ຄົນເຮົາສາມາດຄິດໄດ້ຄືການຈັດຮຽງ ລຳ ດັບຕາມ ລຳ ດັບ. ແຕ່ພວກເຮົາ ຈຳ ເປັນຕ້ອງມອບ ໝາຍ ຈັດລຽງ ລຳ ດັບໃຫ້ກັບຕົວຊີ້ວັດຕົ້ນສະບັບ. ດັ່ງນັ້ນ, ຖ້າພວກເຮົາຈັດຮຽງ ລຳ ດັບທີ່ໃຫ້ໄວ້ໂດຍກົງ, ຫຼັງຈາກນັ້ນພວກເຮົາຈະພາດການສະແດງອອກໃນເບື້ອງຕົ້ນ. ແລະຈະບໍ່ສາມາດຕັດສິນໃຈມອບ ໝາຍ ໜ້າ ທີ່ໃຫ້. ດັ່ງນັ້ນ, ເພື່ອໃຫ້ແນ່ໃຈວ່າພວກເຮົາບໍ່ສູນເສຍຕົວຊີ້ວັດຕົ້ນສະບັບ, ພວກເຮົາສ້າງ vector ຫຼື array ໃໝ່ ທີ່ເກັບຂໍ້ມູນດັດສະນີຕົ້ນສະບັບດ້ວຍຄະແນນ. ພວກເຮົາຈັດຮຽງຫຼື vector ແບບ ໃໝ່ ນີ້. ຫລັງຈາກຈັດປະເພດແລ້ວ, ພວກເຮົາພຽງແຕ່ມອບຫລຽນ ຄຳ, ເງິນແລະຫລຽນທອງໃຫ້ແກ່ບັນດາຜູ້ສະ ໝັກ ທີ່ຕ້ອງການແລະຈັດອັນດັບຈາກ 4 ເຖິງ n, ໃຫ້ແກ່ບັນດາຜູ້ສະ ໝັກ ທີ່ ເໝາະ ສົມ. ພວກເຮົາສາມາດເຮັດສິ່ງນີ້ໄດ້ເພາະວ່າເມື່ອພວກເຮົາຈັດຮຽງຫຼື vector ທີ່ຖືກປັບປ່ຽນ ໃໝ່ ຂອງພວກເຮົາ, ຕົວຊີ້ວັດຕົ້ນສະບັບຍັງປ່ຽນ ຕຳ ແໜ່ງ ຂອງພວກເຂົາທີ່ສອດຄ້ອງກັບຄ່າທີ່ເກັບໄວ້.

ລະຫັດ ສຳ ລັບວິທີແກ້ໄຂບັນຫາ Leetcode

ລະຫັດ C ++ ສຳ ລັບວິທີແກ້ໄຂບັນຫາ Leetcode

#include <bits/stdc++.h>
using namespace std;

vector<string> findRelativeRanks(vector<int>& nums) {
    vector<pair<int,int>> temp;
    int n = nums.size();
    for(int i=0;i<n;i++){
        temp.push_back(make_pair(nums[i], i));
    }
    sort(temp.rbegin(), temp.rend());
    vector<string> answer(n);
    answer[temp[0].second] = "Gold Medal";
    if(n>=2){
        answer[temp[1].second] = "Silver Medal";
    }
    if(n>=3){
        answer[temp[2].second] = "Bronze Medal";
    }
    for(int i=3;i<n;i++)
        answer[temp[i].second] = to_string(i+1);
    return answer;
}

int main(){
    vector<int> nums = {5, 4, 3, 2, 1};
    vector<string> answer = findRelativeRanks(nums);
    for(auto x: answer)cout<<x<<" ";
}
Gold Medal Silver Medal Bronze Medal 4 5

Java code Relative Ranks Leetcode Solution

import java.util.*;
import java.lang.*;
import java.io.*;

class Solution {
  
    public static String[] findRelativeRanks(int[] nums) {
        int n = nums.length;
        int[][] pair = new int[nums.length][2];
        for (int i = 0; i < n; i++) {
            pair[i][0] = nums[i];
            pair[i][1] = i;
        }
        
        Arrays.sort(pair, (a, b) -> (b[0] - a[0]));
        
        String[] result = new String[nums.length];
        result[pair[0][1]] = "Gold Medal";
        if(n>=2)
            result[pair[1][1]] = "Silver Medal";
        if(n>=3)
            result[pair[2][1]] = "Bronze Medal";
        for (int i = 3; i < nums.length; i++) {
            result[pair[i][1]] = Integer.toString(i+1);
        }

        return result;
    }
    
  public static void main (String[] args) throws java.lang.Exception{
    int[] nums = {5, 4, 3, 2, 1};
    String[] answer = findRelativeRanks(nums);
    for(int i=0;i<5;i++)
      System.out.print(answer[i] + " ");
  }
}
Gold Medal Silver Medal Bronze Medal 4 5

ການວິເຄາະຄວາມສັບສົນ

ຄວາມສັບສົນເວລາ

O (NlogN), ເນື່ອງຈາກວ່າການຈັດຮຽງຕ້ອງໃຊ້ເວລາ O (NlogN), ບ່ອນທີ່ N ແມ່ນ ຈຳ ນວນຂອງທາດອົງປະກອບ ion vector ຫຼື array ທີ່ຖືກຈັດຮຽງ.

ຄວາມສັບສົນໃນອະວະກາດ

O (NlogN), ເນື່ອງຈາກວ່າພວກເຮົາໄດ້ໃຊ້ການຈັດຮຽງທີ່ໃຊ້ເວລາຊ່ອງ O (NlogN). ຄວາມສັບສົນຂອງພື້ນທີ່ກໍ່ຄືກັນກັບຄວາມສັບສົນຂອງເວລາ.