美文网首页
1122.数组的相对排序

1122.数组的相对排序

作者: 卖女孩的潇火柴 | 来源:发表于2019-11-03 15:24 被阅读0次

    题目描述

    给你两个数组,arr1 和 arr2,
    arr2 中的元素各不相同
    arr2 中的每个元素都出现在 arr1 中
    对 arr1 中的元素进行排序,使 arr1 中项的相对顺序和 arr2 中的相对顺序相同。未在 arr2 中出现过的元素需要按照升序放在 arr1 的末尾。
    示例:
    输入:arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]
    输出:[2,2,2,1,4,3,3,9,6,7,19]

    Python

    class Solution(object):
        def relativeSortArray(self, arr1, arr2):
            """
            :type arr1: List[int]
            :type arr2: List[int]
            :rtype: List[int]
            """
            arr2 += sorted(set(arr1) -set(arr2))
            returin sorted(arr1, key=arr2.index)
    

    C++

    题目类型:计数排序

    class Solution {
    public:
        vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
            int mask[1001] = {0};
            vector<int> rst;
            for(int i=0; i< arr1.size(); i++){
                mask[arr1[i]]++;
            }
            int index = 0;
            for(int i=0; i< arr2.size(); i++){
                while(mask[arr2[i]]-- > 0){
                    //rst[index++] = arr2[i];
                    rst.push_back(arr2[i]);
                }
            }
            for(int i=0; i<1001; i++){
                while(mask[i]-- > 0){
                    //rst[index++] = i;
                    rst.push_back(i);
                }
            }
            return rst;;
        }
    };
        }
    };
    

    vector数据类型不是很熟悉:
    向量(Vector)是一个封装了动态大小数组的顺序容器(Sequence Container)。跟任意其它类型容器一样,它能够存放各种类型的对象。可以简单的认为,向量是一个能够存放任意类型的动态数组。
    https://www.runoob.com/w3cnote/cpp-vector-container-analysis.html

    相关文章

      网友评论

          本文标题:1122.数组的相对排序

          本文链接:https://www.haomeiwen.com/subject/kwokbctx.html