算法 2.2.2 数组的相对排序【leetcode 1122】

题目描述

给你两个数组，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 中

数据结构

• 数组

算法思维

• 遍历、快速排序、计数排序

解题要点

• 使用自定义的比较器应用于快速排序中
• 使用计数排序，用空间换时间
  
  

解题思路

---

一. Comprehend 理解题意

• arr1 中会存在重复数据，所以不能直接将 arr2 作为 arr1 的开始部分
• 目标是将 arr1 中的元素排序，arr2 其实是作为排序依据
  
  

二. Choose 选择数据结构与算法

自定义比较器 + 快速排序

• 数据结构：数组
• 算法思维：遍历、递归、快速排序

解题思路

• 需要设计一个排序算法，两个值A、B的排序规则为：
  如果 A、B 都出现在 arr2 中，则根据索引顺序比大小
  如果一个在 arr2 中，一个不在 arr2 中，则出现的元素排前面
  如果 A、B 都不在 arr2 中，则根据 A、B 的数值大小确定顺序
  
  

三. Code 编码实现基本解法

class Solution {
    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < arr2.length; i++) {
            map.put(arr2[i], i); //注意：这里写成 map.put(i, arr2[i]) 是不可以的
        }
        quickSort(arr1, 0, arr1.length - 1, map);
        return arr1;
    }

    public void quickSort(int[] target, int low, int high, Map<Integer, Integer> by) {
        int i = low;
        int j = high;
        //基准
        int datum = target[i];
        while (i < j) {
            while (i < j && compare(target[j], datum, by) >= 0) j--;
            if (i < j) target[i++] = target[j];
            while (i < j && compare(target[i], datum, by) <= 0) i++;
            if (i < j) target[j--] = target[i];
        }
        target[i] = datum; //放回基准值
        if (low < i - 1) quickSort(target, low, i - 1, by); //处理左子区
        if (high > i + 1) quickSort(target, i + 1, high, by); //处理右子区
    }

    public int compare(int a, int b, Map<Integer, Integer> map) {
        int o1Index = map.getOrDefault(a, -1);
        int o2Index = map.getOrDefault(b, -1);
        if (o1Index == -1 && o2Index == -1) {
            return a - b;
        } else if (o1Index == -1) {
            return 1;
        } else if (o2Index == -1) {
            return -1;
        } else {
            return o1Index - o2Index;
        }
    }
}

执行耗时：3 ms，击败了 47.25% 的Java用户
内存消耗：38.9 MB，击败了 5.15% 的Java用户

时间复杂度：O(nlogn)
  • 一次快速排序 O(nlogn)
  • map 集合赋值 O(n)

空间复杂度：O(n)
  • n 层递归的内存空间 O(n)
  • map 集合的内存空间 O(n)

四. Consider 思考更优解

改变算法思维：计数排序，以空间换时间

• 因为 arr[i] 为 0-1000，所以开辟一个长1001的数组 nums 用于记录各个数字出现的次数
• 先遍历 arr1，记录各个数字出现的次数
• 再遍历 arr2，对 arr2 中的每个数字按照 nums 中记录的次数依次在新数组 results 中存放
  同时 nums 中针对该数字的次数记录 -1
• 遍历 nums 数组，对于次数不为0的，依次按照次数存放到 results 中
• 返回 results 数组
  
  

五. Code 编码实现最优解

class Solution {
    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        int[] nums = new int[1001];
        for (int i = 0; i < arr1.length; i++) {
            nums[arr1[i]]++;
        }
        int[] results = new int[arr1.length];
        int index = 0;
        for (int i = 0; i < arr2.length; i++) {
            while (nums[arr2[i]] != 0) {
                results[index++] = arr2[i];
                nums[arr2[i]]--;
            }
        }
        for (int i = 0; i < nums.length; i++) {
            while (nums[i] != 0) {
                results[index++] = i;
                nums[i]--;
            }
        }
        return results;
    }
}

执行耗时：0 ms，击败了 100.00% 的Java用户
内存消耗：38.3 MB，击败了 83.57% 的Java用户

时间复杂度：O(n)
  • 三次数组遍历 O(n)

空间复杂度：O(n)
  • 记录数字出现个数的数组的内存空间 O(n)
  • 结果数组的内存空间 O(n)

六. Change 变形与延伸

=== 待续 ===