题目

给定两个数组，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]

提示：1 <= arr1.length, arr2.length <= 1000

0 <= arr1[i], arr2[i] <= 1000

arr2 中的元素 arr2[i] 各不相同

arr2 中的每个元素 arr2[i] 都出现在 arr1 中

注意：本题与主站 1122 题相同：

解题思路分析

1、哈希辅助；时间复杂度O(n)，空间复杂度O(1)

func relativeSortArray(arr1 []int, arr2 []int) []int {
   if len(arr2) == 0 {
      sort.Ints(arr1)
      return arr1
   }
   res := make([]int, 0)
   m := make(map[int]int)
   for i := range arr1 {
      m[arr1[i]]++
   }
   for i := 0; i < len(arr2); i++ {
      for j := 0; j < m[arr2[i]]; j++ {
         res = append(res, arr2[i])
      }
      m[arr2[i]] = 0
   }
   tempArr := make([]int, 0)
   for key, value := range m {
      for value > 0 {
         tempArr = append(tempArr, key)
         value--
      }
   }
   sort.Ints(tempArr)
   res = append(res, tempArr...)
   return res
}

2、暴力法；时间复杂度O(n^2)，空间复杂度O(1)

func relativeSortArray(arr1 []int, arr2 []int) []int {
   count := 0
   for i := 0; i < len(arr2); i++ {
      for j := count; j < len(arr1); j++ {
         if arr2[i] == arr1[j] {
            arr1[count], arr1[j] = arr1[j], arr1[count]
            count++
         }
      }
   }
   sort.Ints(arr1[count:])
   return arr1
}

3、数组辅助；时间复杂度O(n)，空间复杂度O(1)

func relativeSortArray(arr1 []int, arr2 []int) []int {
   temp := make([]int, 1001)
   for i := range arr1 {
      temp[arr1[i]]++
   }
   count := 0
   for i := range arr2 {
      for temp[arr2[i]] > 0 {
         arr1[count] = arr2[i]
         temp[arr2[i]]--
         count++
      }
   }
   for i := 0; i < len(temp); i++ {
      for temp[i] > 0 {
         arr1[count] = i
         temp[i]--
         count++
      }
   }
   return arr1
}

总结

Easy题目，题目同leetcode 1122.数组的相对排序