# # 1122 Relative Sort Array

[LeetCode](https://leetcode.com/problems/relative-sort-array/)

```
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
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://hannahpun.gitbook.io/leetcode-note/set-map/1122-relative-sort-array.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.