Leetcode日记–1122.Relative Sort Array

发布于 2020-11-14  117 次阅读


碎碎念:已经不知道多少次因为Stream的事情被卡住了,哪天钻研一下《Thinking in Java》,争取研究透了以后专门写一篇关于流的文章。

题目如下:

Given two arrays arr1 and arr2, the elements of arr2 are distinct, and all elements in arr2 are also in arr1.

Sort the elements of arr1 such that the relative ordering of items in arr1 are the same as in arr2.  Elements that don't appear in arr2 should be placed at the end of arr1 in ascending order.

Example 1:

Input: arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]
Output: [2,2,2,1,4,3,3,9,6,7,19]

Constraints:

arr1.length, arr2.length <= 1000
0 <= arr1[i], arr2[i] <= 1000
Each arr2[i] is distinct.
Each arr2[i] is in arr1.

思路:

本题就是按照arr2中数字的相对位置对arr1中的数字进行排序,若arr1中的数字在arr2中不存在则在末尾把不存在的数字按照升序进行排序。

方法一:重写数组sort方法中的比较函数

我们可以建立一个Hash Map,其中数字本身为key,数字在arr2中的位置为value。再重写比较函数,使用map的get方法得到两个数的位置,并比较,按照相对位置进行排序。

我一开始实现的代码如下:

    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        Map <Integer,Integer> arr2Map = new HashMap<Integer, Integer>();
        for (int i=0;i<arr2.length;i++) {
            arr2Map.put(arr2[i],i);
        }
        Arrays.sort(arr1,new Comparator<Integer>(){
            public int compare(Integer a,Integer b){
                Integer locationOfa = arr2Map.get(a);
                Integer locationOfb = arr2Map.get(b);
                if (locationOfa==null&&locationOfb==null){
                    return a-b;
                }
                else if (locationOfa==null){
                    return 1;
                }
                else if (locationOfb == null){
                    return  -1;
                }
                else {
                    return locationOfa - locationOfb;
                }
            }
        });
        return arr1;
    }

但是他报了如下的error:

比较器的奇妙报错

报这个错的原因我是在这里找到的,我引用这个老哥在博客中写到的话。

原因是 public static void sort (T [] a,Comparator c) 是根据指定比较器引发的顺序对指定的对象数组进行排序,所以 sort() 方法的第一个参数 T [] a 中只能存放对象,而不能存放基本数据类的数据。如果将 char 类型的数组传入该方法,则会报出以上错误;如果传入的是 Character 类型的数组,则正常。

这里可能有人要问了,char 类型的数据和 Character 类型的数据不是会自动装箱和封箱吗,那为什么这里两者的数组不能通用呢?

通用不代表混用。char 在 Java 中属于八大基本数据类型,不需要实例化就能直接使用;而 Character 是 char 的封装类,需要实例化后才能用。一般来说,char 类型的数据和 Character 类型的数据会动态地进行自动封箱和装箱,来满足不同的需求,但是 char 类型的数组和 Character 类型的数组并不会自动转换啊,它们的本质是数组,只是存放了两种类型的数据而已。

所以如果之前得到的是 char 类型的数组,需要我们自己新建其封装类数组,并将 char 数组的元素全部装入其封装类数组中(这里将元素装入时才会自动封箱)。

也就是说sort方法的第一个参数我们应该传入一个对象数组。在我们这个地方,我们需要将arr1转化为Integer数组。

那么如何把int数组转换为Integer数组呢?我在万能的stackOverflow找到了答案

我们需要把int数组转化为数值流,封装以后,再转为数组,就变成了Integer数组。

int[] data = {1,2,3,4,5,6,7,8,9,10};

// To boxed array
Integer[] what = Arrays.stream( data ).boxed().toArray( Integer[]::new );
Integer[] ever = IntStream.of( data ).boxed().toArray( Integer[]::new );

// To boxed list
List<Integer> you  = Arrays.stream( data ).boxed().collect( Collectors.toList() );
List<Integer> like = IntStream.of( data ).boxed().collect( Collectors.toList() );

因此改进后的重写比较器代码为:

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);
    }

    return Arrays.stream(arr1).boxed().sorted(new Comparator<Integer>() {
        public int compare(Integer a, Integer b) {
            Integer indexa = map.get(a);
            Integer indexb = map.get(b);
            if(indexa == null && indexb == null) {
                return a-b;
            } else if (indexa == null) {
                return 1;
            } else if (indexb == null) {
                return -1;
            } else {
                return map.get(a) - map.get(b);    
            }
        }            
    }).mapToInt(i->i).toArray();
}

该方法的时间复杂度为O(mlogm+n),m和n分别为arr1和arr2的长度。第一项为arr1的排序时间复杂度,第二项为arr2构造hashMap的时间复杂度。

空间复杂度为O(logm+n),其中排序需要的栈空间为logm,Hash Map需要的空间为n。

方法二:类似于计数排序

说到这里,我的JAVA实现十种基础排序算法好像一直咕咕咕到现在还没写完...

我们可以使用一个frequency数组,在frequency[x]处记下数字x出现了多少次。然后再次遍历arr2数组,没遇到一个数arr2[i],就查询在frequency[arr2[i]]中其出现的次数,并填充进入res数组中,再将已经放入res的frequency[x]值置为0。

遍历完arr2数组后,我们再次遍历一遍frequency数组,把没有置为0的按顺序放入res中。

class Solution {
    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        int upper = 0;
        for (int x : arr1) {
            upper = Math.max(upper, x);
        }
        int[] frequency = new int[upper + 1];
        for (int x : arr1) {
            ++frequency[x];
        }
        int[] ans = new int[arr1.length];
        int index = 0;
        for (int x : arr2) {
            for (int i = 0; i < frequency[x]; ++i) {
                ans[index++] = x;
            }
            frequency[x] = 0;
        }
        for (int x = 0; x <= upper; ++x) {
            for (int i = 0; i < frequency[x]; ++i) {
                ans[index++] = x;
            }
        }
        return ans;
    }
}

作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/relative-sort-array/solution/shu-zu-de-xiang-dui-pai-xu-by-leetcode-solution/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

时间复杂度:O(m+n+upper),其中 m 和 n 分别是数组 arr1和arr2的长度,upper 是数组arr1中的最大值,在本题中 upper 不会超过 1000。遍历数组 arr2
的时间复杂度为 O(n),遍历数组frequency 的时间复杂度为O(upper),而在遍历的过程中,我们一共需要 O(m) 的时间得到答案数组。

空间复杂度:O(upper),即为数组 frequency 需要使用的空间。


你好哇!欢迎来到雷公马碎碎念的地方:)