LeetCode.1122-相对排序数组(Relative Sort Array)

佚名 5年前 (2019-07-30) 算法 1009人围观抢沙发百度已收录

这是小川的第393次更新，第427篇原创

01 看题和准备

今天介绍的是LeetCode算法题中Easy级别的第258题（顺位题号是1122）。给定两个数组arr1和arr2，arr2中的元素是不同的，arr2中的所有元素也在arr1中。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

对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[i]都是不同的。
每个arr2[i]都在arr1中。

02 第一种解法

题目的意思是对arr1分两部分排序，前部分的顺序要和arr2中元素的顺序一样，剩余不是arr2中的元素，要按照增序排列。

直接翻译题目即可，利用一个HashMap，将arr2中的元素值作为key，因为arr2中的元素不会重复出现，将value设统一值0，接着遍历arr1，如果当前元素在HashMap中存在，就计数出现的次数，赋值到value上，反之就将其存入ArrayList中。遍历arr2，将对应的元素写入到结果数组中，出现几次就写入几次。最后，如果ArrayList中有剩余未处理的数据，就将其排序，再写入到结果数组中去。

此解法的时间复杂度是O(N)，最坏的情况可能到O(N^2)，空间复杂度是O(N)。

public int[] relativeSortArray(int[] arr1, int[] arr2) {
    int[] result = new int[arr1.length];
    List<Integer> left = new ArrayList<Integer>();
    Map<Integer, Integer> map = new HashMap<Integer, Integer>();
    for (int num : arr2) {
        map.put(num, 0);
    }
    for (int num : arr1) {
        if (map.containsKey(num)) {
            map.put(num, map.getOrDefault(num, 0)+1);
        } else {
            left.add(num);
        }
    }
    int index = 0, i = 0;
    while (i<result.length && index<arr2.length) {
        int count = map.get(arr2[index]);
        while (count > 0) {
            result[i++] = arr2[index];
            count--;
        }
        index++;
    }
    if (left.size() > 0) {
        Collections.sort(left);
        for (int j=0; j<left.size(); j++) {
            result[i++] = left.get(j);
        }
    }
    return result;
}

03 第二种解法

我们也可以使用计数排序算法，简化计算步骤。

此解法的时间复杂度是O(N)，空间复杂度是O(N)。

public int[] relativeSortArray2(int[] arr1, int[] arr2) {
    int[] count = new int[1001];
    // 遍历arr1中的元素并计数
    for (int num : arr1) {
        count[num]++;
    }
    int index = 0;
    // 处理arr2中的元素
    for (int num : arr2) {
        while (count[num] > 0) {
            arr1[index++] = num;
            count[num]--;
        }
    }
    // 处理剩余不是arr2中的元素
    for (int i=0; i<count.length; i++) {
        while (count[i] > 0) {
            arr1[index++] = i;
            count[i]--;
        }
    }
    return arr1;
}

04 第三种解法

我们也可以直接重写排序方法。

此解法的时间复杂度是O(N log(N))，最坏的情况可能到O(N^2 log(N))，空间复杂度是O(N)。

public int[] relativeSortArray3(int[] arr1, int[] arr2) {
    Map<Integer, Integer> map = new HashMap<Integer, Integer>();
    for (int i=0; i<arr2.length; i++) {
        map.put(arr2[i], i);
    }
    // 为方便后面排序，将arr1转成Integer类型的数组
    Integer[] sort = new Integer[arr1.length];
    for (int i=0; i<sort.length; i++) {
        sort[i] = arr1[i];
    }
    Arrays.sort(sort, new Comparator<Integer>() {

        @Override
        public int compare(Integer a, Integer b) {
            // a和b都不是arr2中的元素
            if (!map.containsKey(a) && !map.containsKey(b)) {
                return a - b;
            }
            // 不能直接使用map.get(key)，会报空指针
            return map.getOrDefault(a, arr1.length) - 
                    map.getOrDefault(b, arr1.length);
        }
    });
    // 将排序后的sort数组元素回写到arr1中去
    for (int i=0; i<arr1.length; i++) {
        arr1[i] = sort[i];
    }
    return arr1;
}