Home | Projects | Notes > Problem Solving > LC - E - 1122. Relative Sort Array (map, multiset)

LC - E - 1122. Relative Sort Array (map, multiset)

Solutions in C++

Solution 1

This solution uses STL map container.

Complexity Analysis:

• $T=O(n)$$T = O(n)$ where $n$$n$ is the length of the given vector arr1

• $S=O(n)$$S = O(n)$ as additional memory is used for map

Solution:

xxxxxxxxxx
27
1
class Solution {
2
public:
3
    vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
4
        map<int, int> m;
5

6
        for (auto n : arr1)
7
            m[n]++;
8

9
        arr1.clear();
10

11
        for (auto n : arr2)
12
        {
13
            while (m[n]-- > 0)
14
                arr1.push_back(n);
15
            
16
            m.erase(n);
17
        }
18

19
        for (auto p : m)
20
        {
21
            while (p.second-- > 0)
22
                arr1.push_back(p.first);
23
        }
24

25
        return arr1;
26
    }
27
};

Solution 2

This solution uses STL multiset container.

Complexity Analysis:

• $T=O(n)$$T = O(n)$ where $n$$n$ is the length of the given vector arr1

• $S=O(n)$$S = O(n)$ as additional memory is used for multiset

Solution:

xxxxxxxxxx
27
1
class Solution {
2
public:
3
    vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
4
        multiset<int> ms;
5

6
        for (auto n : arr1)
7
            ms.insert(n);
8

9
        arr1.clear();
10

11
        for (auto n : arr2)
12
        {
13
            auto pos = ms.find(n);
14
            while (pos != ms.end())
15
            {
16
                arr1.push_back(n);
17
                ms.erase(pos);
18
                pos = ms.find(n);
19
            }
20
        }
21

22
        for (auto n : ms)
23
            arr1.push_back(n);
24

25
        return arr1;
26
    }
27
};