# 1122.Relative-Sort-Array

## 1122. Relative Sort Array

## 题目地址

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

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

## 代码

### Approach #1 Replace elements according to the count

Time: O(1) && Space: O(1)

```java
class Solution {
  public int[] relativeSortArray(int[] arr1, int[] arr2) {
        int[] cnt = new int[1001];
    for (int n: arr1)     cnt[n]++;
    int i = 0;
    for (int n : arr2) {
      while (cnt[n]-- > 0) {
        arr1[i++] = n;
      }
    }
    for (int n = 0; n < cnt.length; n++) {
      while (cnt[n]-- > 0) {
        arr1[i++] = n;
      }
    }
    return arr1;
  }
}
```

### Approach #2 TreeMap

```java
class Solution {
  public int[] relativeSortArray(int[] arr1, int arr2) {
    TreeMap<Integer, Integer> map = new TreeMap();
    for (int n: arr1)     map.put(n, map.getOrDefault(n, 0) + 1);
    int i = 0;
    for (int n: arr2) {
      while (map.get(n) > 0) {
        arr1[i++] = n;
        map.put(n, map.get(n) - 1);
      }
    }

    for (int n: map.keySet()) {
      while (map.get(n) > 0) {
        arr1[i++] = n;
        map.put(n, map.get(n) - 1);
      }
    }

    return arr1;
  }
}
```


---

# 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://wentao-shao.gitbook.io/leetcode/array/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.