力扣 075

LCR 075. 数组的相对排序

给定两个数组，arr1 和 arr2，

• arr2 中的元素各不相同
• arr2 中的每个元素都出现在 arr1 中

对 arr1 中的元素进行排序，使 arr1 中项的相对顺序和 arr2 中的相对顺序相同。未在 arr2 中出现过的元素需要按照升序放在 arr1 的末尾。

利用map计数，想的过于复杂，后续看如何优化。

复杂度

• 时间复杂度: 击败100%
• 空间复杂度: 7.9MB 击败5%

class Solution {
public:
    vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
        map<int,int> num;
        for(auto i: arr2){
            // t.insert(pair<int, string>(0, "one"));
            num[i]=0;
        }
        vector<int>res1,res;
        for(int i:arr1){
            if(num.count(i)==0){
                res1.push_back(i);
            }else{
                num[i]+=1;
            }
        }
        for(int i:arr2){
            for(int j=0;j<num[i];j++){
                res.push_back(i);
            }
        }
        sort(res1.begin(),res1.end());
        for(auto i:res1){
            res.push_back(i);
        }
        return res;

    }
};

作者：wu-xian-5a

链接：https://leetcode.cn/problems/0H97ZC/solution/li-yong-mapji-shu-by-wu-xian-5a-lfcf/

来源：力扣（LeetCode）

著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。