daily_leetcode_2020_1114_1122._数组的相对排序

1 题目描述

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

2 双指针

此题的双指针实际上就是一种暴力手段，由于arr2中的元素是不重复的，所以在遍历arr2(arr2_point)时对于当前元素x, 当它在arr1中出现，就把它移到arr1前面(这个位置用arr1_point)，然后arr_point向前移动一位，

   def relativeSortArray(self, arr1, arr2):

        """ 双指针 """
        arr1_len = len(arr1)
        arr2_len = len(arr2)

        arr1_point = 0  # arr1指针
        for arr2_point in range(arr2_len):
            for i in range(arr1_point, arr1_len):
                if arr1[i] == arr2[arr2_point]:
                    arr1[i], arr1[arr1_point] = arr1[arr1_point], arr1[i]
                    arr1_point += 1

        """ arr1剩下的排序 """
        for i in range(arr1_point, arr1_len):
            for j in range(arr1_point, arr1_len):
                if arr1[i] < arr1[j]:
                    arr1[i], arr1[j] = arr1[j], arr1[i]
        # print(arr1)
        return arr1

3 自定义排序

自定义排序意味着我们只需要设计好排序函数就可以了。

在排序函数中，问题的关键在于：

1. 对对arr2中的那些数在arr1中怎么区分大小
2. 如何区分arr1中在arr2中出现的和没有出现的 大小

对于第一个问题，很容易想到返回该元素在arr2中的下标不就好了，这意味这我们需要对arr2构造一个map, 对元素x,x->index.

第二个问题，我们可以考虑将arr2的元素整体缩小，那么我们就在构造字典的时候用下标除arr2的长，那么肯定是0-1之间，保证了和arr1的大小区分。

代码：

    def diy_sort(self, arr1, arr2):

        arr2_len = len(arr2)
        arr2_map = {val: index/arr2_len for index, val in enumerate(arr2)}

        def get_val(x):
            return arr2_map[x] if x in arr2_map else x

        arr1.sort(key=get_val)
        return arr1

4 计数排序

由于元素的范围在[0,1000], 可以使用一个数组freq 来存储arr1中每个元素的出现次数。当我们遍历arr2时，对于元素x,我们向res中加入freq[x]个x。当遍历完arr2时，res中得数已经是根据arr2中得元素排好序的；最后，我们将arr1中没有在arr2中出现的数都加入res中，返回res.

代码：

    def count_sort(self, arr1, arr2):

        res = []
        """ 实际上我们可以开小一点的 """
        max_value = max(arr1)
        freq = [0] * (max_value + 1)

        """ 统计arr1 元素的 freq """
        for val in arr1:
            freq[val] += 1

        """ 遍历 arr2, 将其在 arr1 中出现的加入 res """
        for val in arr2:
            res.extend([val] * freq[val])
            freq[val] = 0  # 将出现的mark掉，后面还要对没有出现的排序

        """ 将arr1 中剩下的 加入到res """
        for index in range(max_value + 1):
            if freq[index] > 0:
                res.extend([index] * freq[index])

        print(res)
        return res