[LeetCode] 1122. Relative Sort Array 数组的相对排序
Given two arrays arr1
and arr2
, the elements of arr2
are distinct, and all elements in arr2
are also in arr1
.
Sort the elements of arr1
such that the relative ordering of items in arr1
are the same as in arr2
. Elements that don't appear in arr2
should be placed at the end of arr1
in ascending order.
Example 1:
Input: arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]
Output: [2,2,2,1,4,3,3,9,6,7,19]
Constraints:
1 <= arr1.length, arr2.length <= 1000
0 <= arr1[i], arr2[i] <= 1000
- All the elements of
arr2
are distinct. - Each
arr2[i]
is inarr1
.
这道题说是有两个数组 arr1 和 arr2,其中 arr2 中的所有数字均在 arr1 中,现在让给 arr1 重新排序,使得其按照 arr2 中数字的顺序排列,将不在 arr2 中的数字按照大小顺序排在末尾,题目中给的例子可以很好的帮助我们理解题意。由于 arr1 中可能出现重复数字,而相同的数字是要排在一起的,所以需要统计 arr1 中每个数字出现的次数,又因为最后还需要将不在 arr2 中的数字按顺序排列,那么这里用个 TreeMap 是坠好的,既能统计个数,又能排序,简直太棒了。用 TreeMap 统计好 arr1 中数字的个数之后,然后遍历 arr2,将其中每个数字在之前的 TreeMap 中找到对应的次数,并在结果 res 中加入相同次数的数字进去,之后在 TreeMap 中移除该数字。这样遍历完 arr2 之后,在 TreeMap 中剩下的数字就是仅存在于 arr1 的,且还是有序的,可以直接按顺序加入到结果 res 中即可,参见代码如下:
class Solution {
public:
vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
vector<int> res;
map<int, int> m;
for (int num : arr1) ++m[num];
for (int num : arr2) {
for (int i = 0; i < m[num]; ++i) {
res.push_back(num);
}
m.erase(num);
}
for (auto a : m) {
for (int i = 0; i < a.second; ++i) {
res.push_back(a.first);
}
}
return res;
}
};
Github 同步地址:
https://github.com/grandyang/leetcode/issues/1122
参考资料:
https://leetcode.com/problems/relative-sort-array/
相关文章
- Leetcode: 3Sum
- LeetCode高频题34. 在排序数组中查找元素的第一个和最后一个位置
- LeetCode高频题33. 搜索旋转排序数组
- 后缀数组的应用:[Leetcode]1062. 最长重复子串(困难)
- JS Leetcode 154. 寻找旋转排序数组中的最小值 II 题解分析
- JS leetcode 找到所有数组中消失的数字 题解分析
- LeetCode搜索二叉树的练习
- 155、【动态规划】leetcode ——474. 一和零:三维数组+二维滚动数组(C++版本)
- 73、【数组】leetcode——15. 三数之和(C++/Python版本)
- 68、【哈希表】leetcode——349. 两个数组的交集(C++版本)
- [LeetCode] 1296. Divide Array in Sets of K Consecutive Numbers 划分数组为连续数字的集合
- [LeetCode] 999. Available Captures for Rook 国际象棋中车的可捕获量
- [LeetCode] 987. Vertical Order Traversal of a Binary Tree 竖直遍历二叉树
- [LeetCode] 780. Reaching Points 到达指定点
- [LeetCode] Single Element in a Sorted Array 有序数组中的单独元素
- [LeetCode] Shuffle an Array 数组洗牌
- [LeetCode] 350. Intersection of Two Arrays II 两个数组相交之二
- LeetCode将有序数组转换为二叉搜索树
- leetcode 153. Find Minimum in Rotated Sorted Array 寻找旋转排序数组中的最小值(中)