# 1122 Relative Sort Array

善用 Map 是有排序的特性

LeetCode

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.

input: 兩個數字 Array，arr 2 的全部包含在 arr 2，arr 裡面是不重覆值
output: 回傳一個大陣列，照著 arr 2 順序排列，arr2 不存在就接在最後

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.

/**
 * @param {number[]} arr1
 * @param {number[]} arr2
 * @return {number[]}
 */
var relativeSortArray = function(arr1, arr2) {
    
};

怎麼解

我一開始是這樣想，兩個陣列都沒排序，我會用 map 先存總共有幾個然後再印出來

var relativeSortArray = function(arr1, arr2) {
  let newMap = new Map();
  let notInArr2 = [];
  let result = [];
  arr2.forEach(item => {
    newMap.set(item, 0)
  })
  arr1.forEach(item => {
    if(newMap.has(item)){
      newMap.set(item, newMap.get(item) + 1)
    }else{
      notInArr2.push(item)
    }
  })
  newMap.forEach((val, key) => {
    for(let i = 0; i< val; i++){
      result.push(key)
    }
  })
 
  return result.concat(notInArr2.sort((a,b)=> a - b))
};

console.log(relativeSortArray([2,3,1,3,2,4,6,7,9,2,19],[2,1,4,3,9,6]))
// faster than 6.09% of JavaScript online submissions

結果速度才 6%，一定有更好解法(也是合理我已經不知道寫了幾個迴圈了)

改善

這題改善解法概念其實一模一樣，只是幾個地方做調整

• arr1 在一開始先 sort

• Map 的特性是有順序的，所以善用這個特性，arr2 在一開始就存進去所以 map 會照這個順序走

• 把 notInArr2 拿掉，可以一起存進 newMap，而且因為 arr1 排序過所以他自然會被放在後面

var relativeSortArray = function(arr1, arr2) {
  let newMap = new Map();
  let result = [];

  arr1.sort( (a, b) => a - b );

  
  arr2.forEach(item => {
    newMap.set(item, 0)
  })
  
  arr1.forEach(item => {
    if(newMap.has(item)){
      newMap.set(item, newMap.get(item) + 1)
    }else{
      newMap.set(item, 1)
    }
  })


  newMap.forEach((val, key) => {
    for(let i = 0; i< val; i++){
      result.push(key)
    }
  })
 
  return result;
};

console.log(relativeSortArray([2,3,1,3,2,4,6,7,9,2,19],[2,1,4,3,9,6]))
// faster than 81.21% of JavaScript online submissions