Leetcode Day3 數組相對排序+數組中的第k大的數字+連結清單排序

1、數組相對排序

給定兩個數組，arr1 和 arr2，

arr2 中的元素各不相同

arr2 中的每個元素都出現在 arr1 中

對 arr1 中的元素進行排序，使 arr1 中項的相對順序和 arr2 中的相對順序相同。未在 arr2 中出現過的元素需要按照升序放在 arr1 的末尾。

AC代碼

class Solution {
public:
   
    struct Num{
        int index=INT_MAX;
        int value;
    };
    static bool com(Num a,Num b){
        if(a.index!=b.index){
            return a.index<b.index;
        }else{
            return a.value<b.value;
        }
    }
    vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
        int n=arr1.size();
        vector<Num>nums(n);
        map<int,int>mp;
        int m=arr2.size();
        for(int i=0;i<m;i++){
            mp[arr2[i]]=i;
        }
        for(int i=0;i<n;i++){
            nums[i].value=arr1[i];
            if(mp.find(arr1[i])!=mp.end()){
                nums[i].index=mp[arr1[i]];
            }
        }
        sort(nums.begin(),nums.end(),com);
        for(int i=0;i<n;i++){
            arr1[i]=nums[i].value;
        }
        return arr1;
    }
};
           

2、數組中的第k大的數字

給定整數數組 nums 和整數 k，請傳回數組中第 k 個最大的元素。

請注意，你需要找的是數組排序後的第 k 個最大的元素，而不是第 k 個不同的元素。

思路：排序後直接輸出第k大的數字即可，不考慮重複的問題

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        sort(nums.begin(),nums.end());
    
        int n=nums.size();

        return nums[n-k];
        
    }
};
           

3、連結清單排序

給定連結清單的頭結點 head ，請将其按 升序 排列并傳回 排序後的連結清單 。

思路：本質是利用周遊連結清單擷取數組，sort直接無腦排序後将數組的資料更新給連結清單

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        ListNode* p=head;
        vector<int>nums;
        while(p!=NULL){
            nums.push_back(p->val);
            p=p->next;
        }
        sort(nums.begin(),nums.end());
        p=head;
        int i=0;
        while(p!=NULL){
            p->val=nums[i++];
            p=p->next;
        }
        return head;
    }
};