Leetcode-1122-数组的相对排序

Leecode-1122-数组的相对排序https://leetcode-cn.com/problems/maximum-nesting-depth-of-two-valid-parentheses-strings/)

题目描述

给你两个数组，arr1 和 arr2，

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

示例：

输入：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 中

方法 ： 计数排序

• 注意到本题中元素的范围为 [0, 1000][0,1000]，这个范围不是很大，我们也可以考虑不基于比较的排序，例如「计数排序」。

具体算法

1. 使用长度为1001【下标0 - 1000】 的数组frequency 记录每一个元素在arr1 中出现的次数

2. 随后遍历数组arr2,当遍历到元素x的时候。将frequency[x] 放入到结果集中，并将frequency[x]清0

3. 此时还剩下没有在arr2 中出现过的元素，因此我们还需要对整个数组frequency 进行一次遍历。当遍历到x时，如果frequency[x]!=0 ，说明这个元素没有在arr2中出现，那么将这个元素添加到答案的最后。

class Solution {
    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        // 本题中元素的范围是[0,1000] 这个范围不是很大，可以不考虑比较排序，例如【计数排序】
        // 对空间的优化，使用比数组arr1中最大值upper 使用长度upper + 1;
        int upper = 0;
        for(int x:arr1){
            upper = Math.max(upper,x);
        }

        // 记录每个数出现的次数
        int[] frequency = new int[upper + 1];
        for(int x:arr1){
            ++frequency[x];
        }

        // 遍历数组arr2，当遍历到元素x的时候
        // 将frequency[x] 放入到结果集中，并将frequency[x]清0
        int[] ans = new int[arr1.length];
        int idx = 0;
        for(int x:arr2){
            for(int i = 0;i < frequency[x];i++){
                ans[idx++] = x;
            }
            frequency[x] = 0;
        }

        // 将frequency[x]中剩余的数字放入到结果集中
        // 按照frequency中的升序放入
        for(int x = 0;x <= upper;++x){
            for(int i = 0;i < frequency[x];++i){
                ans[idx++] = x;
            }
        }
         // 返回结果
        return ans; 
    }
}

复杂度分析

• 时间复杂度：O(m + n + upper)
• 空间复杂度 : O(upper),即为frequency数组使用的空间

打赏