“This is the 11th day of my participation in the First Challenge 2022. For details: First Challenge 2022”

[B] [C] [D]

I give you two arrays, arr1 and arR2,

  • arr2The elements in the
  • arr2Each element in thearr1Β δΈ­

Sort the elements in ARR1 so that the relative order of the items in ARR1 is the same as that in ARR2. Elements that do not appear in ARR2 need to be placed at the end of ARR1 in ascending order.

Example:

Input: arr1 =,3,1,3,2,4,6,7,9,2,19 [2], arr2 =,1,4,3,9,6 [2] output:,2,2,1,4,3,3,9,6,7,19 [2]Copy the code

Tip:

  • 1 <= arr1.length, arr2.length <= 1000
  • 0 <= arr1[i], arr2[i] <= 1000
  • arr2The elements in thearr2[i]Each are not identical
  • arr2Each element inarr2[i]inarr1Β δΈ­

Their thinking

Since the elements in this array are integers greater than or equal to 0, we can use counting sort to solve the problem. If you don’t know anything about counting sort, you can read my previous video do you really know anything about sorting? This article, we will not repeat here. First we create an extra storage space temp array to record the number of occurrences of each number in arR1 array. Next, we need to iterate through the ARR2 array. According to the order of the elements in the ARR2 array, we insert the elements that also appear in ARR1 into the result array according to the order in which they appear in ARR2, combined with the number of occurrences of each number. We then iterate through the TEMP array, placing the unprocessed elements in ascending order at the end of the result array, and we are done sorting ARr1.

Code implementation

Var relativeSortArray = function(arr1, arr2) {var relativeSortArray = function(arr1, arr2) {const temp = [] // Iterate through the input array and count for(let I = 0; i<arr1.length; I ++){const num = arr1[I] if(temp[num]===undefined) temp[num]= 1 else temp[num]++ Put the same elements in arr1 for(let I = 0; i<arr2.length; I ++){const num = arr2[I] while(temp[num]){res.push(num) temp[num]--}} for(let I = 0; i<temp.length; I ++){if(temp[I]===0) continue while(temp[I]){res.push(I) temp[I]--}} };Copy the code

This completes the relative sorting of the Leetcode-1122 – array

If you have any questions or suggestions, please leave a comment! πŸ‘ 🏻 πŸ‘ 🏻 πŸ‘ 🏻