go语言题解LeetCode1122数组的相对排序

目录

题目描述

1122. 数组的相对排序 - 力扣（LeetCode）

给你两个数组，arr1 和 arr2，arr2 中的元素各不相同，arr2 中的每个元素都出现在 arr1 中。

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

示例 1：

输入：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]
复制代码

示例 2:

输入：arr1 = [28,6,22,8,44,17], arr2 = [22,28,8,6]
输出：[22,28,8,6,17,44]
复制代码

提示：

• 1 <= arr1.length, arr2.length <= 1000
• 0 <= arr1[i], arr2[i] <= 1000
• arr2 中的元素 arr2[i] 各不相同
• arr2 中的每个元素 arr2[i] 都出现在 arr1 中

思路分析

最简单的就是 暴力法 了

解题思路

利用双循环将数组1的数字依次与数组二相比较，相同则与前面元素交换位置

数组1中剩余元素利用sort函数进行排序即可

vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
        int tmp = 0;
        for(int i = 0;i<arr2.size();++i)
           for(int j = 0;j<arr1.size();++j){
               if(arr1[j] == arr2[i]){
                     swap(arr1[j],arr1[tmp]);
                     ++tmp;
               }
           }
           sort(arr1.begin()+tmp,arr1.end());
           return arr1;
    }
复制代码

还有就是 计数排序

解题思路

与递增递减排序不同，本题是根据数组顺序自定义排序，因此最适合计数排序来实现（桶排序）

因为题意说明数组中元素在0~1000之间，因此定义一个容量为1000的桶

第一个循环对数组1中的元素进行计数，结果保存在桶中

第二个循环通过数组2，将重合的元素从数组1的0位置开始插入

第三个循环，搜索桶中剩余的数组1元素，并把它们插入到数组1的后面。

vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) 
{
        vector<int> count(1001);
        for (int i = 0; i<arr1.size(); i++)
        {
                count[arr1[i]]++;
        }
        int k = 0;
        for (int i = 0; i<arr2.size(); i++)
        {
                while (count[arr2[i]]>0)
                {
                        arr1[k++] = arr2[i];
                        count[arr2[i]]--;
                }
        }
        for (int i = 0; i < count.size(); i++)
        {
                while (count[i] >0)
                {
                        arr1[k++] = i;
                        count[i]--;
                }
        }
        return arr1;
}

以上就是go语言题解LeetCode1122数组的相对排序的详细内容，更多关于go语言数组相对排序的资料请关注其它相关文章！

原文地址：https://juejin.cn/post/7182149630363172921