1122. 数组的相对排序
难度简单227
给你两个数组，arr1 和 arr2，arr2 中的元素各不相同，arr2 中的每个元素都出现在 arr1 中。
对 arr1 中的元素进行排序，使 arr1 中项的相对顺序和 arr2 中的相对顺序相同。未在 arr2 中出现过的元素需要按照升序放在 arr1 的末尾。
示例 1：
代码语言：javascript复制输入：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:
代码语言：javascript复制输入：arr1 = [28,6,22,8,44,17], arr2 = [22,28,8,6]
输出：[22,28,8,6,17,44]提示：
1 <= arr1.length, arr2.length <= 10000 <= arr1[i], arr2[i] <= 1000arr2中的元素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;
}
};
