给你两个数组,arr1 和 arr2,arr2 中的元素各不相同,arr2 中的每个元素都出现在 arr1 中。 对 arr1 中的元素进行排序,使 arr1 中项的相对顺序和 arr2 中的相对顺序相同。未在 arr2 中出现过的元素需要按照升序放在 arr1 的末尾用C++编写
时间: 2024-03-25 18:39:55 浏览: 18
可以使用桶排序的思想来解决这个问题。
首先,我们可以遍历一遍 arr1,统计每个元素出现的次数,然后按照 arr2 中元素的顺序,将 arr1 中的元素排序。具体实现步骤如下:
1. 遍历 arr1,统计每个元素出现的次数,使用 unordered_map<int, int> count 来存储。
2. 遍历 arr2,将 arr2 中的元素按照出现次数依次插入到结果数组中。
3. 遍历 count,将未出现在 arr2 中的元素按照升序插入到结果数组的末尾。
C++ 代码实现如下:
```c++
#include <unordered_map>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
unordered_map<int, int> count;
vector<int> res;
// 统计 arr1 中每个元素出现的次数
for (int num : arr1) {
count[num]++;
}
// 将 arr2 中的元素按照出现次数依次插入到结果数组中
for (int num : arr2) {
int c = count[num];
while (c--) {
res.push_back(num);
}
count.erase(num);
}
// 将未出现在 arr2 中的元素按照升序插入到结果数组的末尾
vector<int> rest;
for (auto& p : count) {
int num = p.first;
int c = p.second;
while (c--) {
rest.push_back(num);
}
}
sort(rest.begin(), rest.end());
res.insert(res.end(), rest.begin(), rest.end());
return res;
}
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)