leetcode每日一题：数组的相对排序

利刃大大

发布于 2023-04-12 14:13:50

1520

发布于 2023-04-12 14:13:50

文章被收录于专栏：编程语言/linux/算法

1122. 数组的相对排序

难度简单227

给你两个数组，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 中

思路一：暴力解法

先对 arr2 中出现的部分，在 arr1 中进行交换处理：运用循环，将 arr2 中的每一个元素在 arr1 中遍历一遍，进行查找，并且依次往前面放，知道 arr2 遍历完成
接着就对 arr2 的剩余部分进行排序，这里用的方法是冒泡排序法，也可以直接调用函数进行解决。

class Solution {
public:
    vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
        //对 arr2 中出现的元素，在 arr1 中查找并且向前放
        int cur = 0;
        for(int j = 0; j < arr2.size(); ++j)
        {
            int i = cur;
            while(i < arr1.size())
            {
                if(arr1[i] == arr2[j])
                {
                    swap(arr1[cur], arr1[i]);
                    cur++;
                }
                ++i;
            }
        }
        
        //对剩下的元素进行排序
        int i = 0;
        for(int j = cur; j < arr1.size() - 1; ++j,++i)
        {
            int flag = 1;
            for(int k = cur; k < arr1.size() - 1 - i; ++k)
            {
                if(arr1[k] > arr1[k + 1])
                {
                    swap(arr1[k], arr1[k + 1]);
                    flag = 0;
                }
            }
            if(flag == 1)
                break;
        }
        return arr1;
    }
};

思路二：计数排序

因为这道题中提示，一共最多有1000个元素，比较少，所以可以用计数排序的方法来解决。

这道题还可以优化一下，可以不用创建1000个int大小的空间，只需要找出 arr1 中最大的数，然后开辟一个 [ 0 , max + 1]大小的数组即可。

首先先找出 arr1 中最大的元素 Max，然后开辟一个 Max+1 大小的数组 tmp
然后用 tmp 计算 arr1 中出现元素的个数
再创建一个用于返回数组的 ans，将 arr2 中出现的数字以 tmp 中出现的次数个数依次放到 ans 中去
最后再对 tmp 中剩余的不为0的数，尾插到 ans 后面去。（因为计数排序是从小到大排，所以无需再排序了）

class Solution {
public:
    vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
        //找到arr1中最大的数，创建一个大小为 Max+1 的数组tmp即可
        int Max = *max_element(arr1.begin(), arr1.end());
        vector<int> tmp (Max + 1, 0);

        for(int i = 0; i < arr1.size(); ++i)
        {
            tmp[arr1[i]]++;
        }

        //将arr2中出现的数字以tmp中出现的次数放到ans中去
        vector<int> ans;
        for(int i = 0; i < arr2.size(); ++i)
        {
            while(tmp[arr2[i]]-- > 0)
            {
                ans.push_back(arr2[i]);
            }
        }

        //将tmp中剩余的次数对应的数字放到arr1末尾
        for(int i = 0; i <= Max; ++i)
        {
            while((tmp[i]--) > 0)
            {
                ans.push_back(i);
            }
        }
        return ans;
    }
};

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022-07-25，如有侵权请联系 cloudcommunity@tencent.com 删除

leetcode