Keshawn_lu's Blog

Leetcode 1122. 数组的相对排序

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

题目简介：

给你两个数组，arr1 和 arr2，

  • 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. 代码如下：
Total : 424
2023
2022
2021
2020
2019
动态规划 树 深度优先搜索 哈希表 数组 深度优先遍历 单调栈 字符串 双指针 栈 贪心 图 模拟 广度优先搜索 回溯 滑动窗口 二分查找 广度优先遍历 记忆化搜索 数学 链表 前缀和 双向链表 优先队列 拓扑排序 KMP 堆 字典树 递归 并查集 矩阵 位运算 双端队列 吴恩达团队NLP 吴恩达深度学习 线性表
杂谈 算法相关 PAT 2019推理小说阅读计划 NLP 深度学习 大三课程学习 大四课程学习 浙工商OJ 牛客网