Keshawn_lu's Blog

Leetcode 1122. 数组的相对排序

字数统计: 352阅读时长: 1 min
2020/11/14 Share

题目简介:

给你两个数组,arr1arr2

  • arr2 中的元素各不相同
  • arr2 中的每个元素都出现在 arr1

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

示例:

1
2
输入: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]

提示:

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

思路:

计数排序,首先将arr1中元素出现的次数进行计数,存入count数组中;然后根据arr2中的元素相对位置将arr1的元素依次存入答案数组中。

最后遍历count数组,将其中count[i] > 0的元素存入答案数组(以升序存入)。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {

int count[1001] = {0};
vector<int> res;

for(int i = 0; i < arr1.size(); i++){

count[arr1[i]]++; //计数
}

for(int i = 0; i < arr2.size(); i++){

while(count[arr2[i]] > 0){

res.push_back(arr2[i]);
count[arr2[i]]--;
}
}

for(int i = 0; i < 1001; i++){

while(count[i] > 0){

res.push_back(i);
count[i]--;
}
}

return res;
}
};
CATALOG
  1. 1. 题目简介:
  2. 2. 思路:
  3. 3. 代码如下: