Relative Sort Array

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]

Approach

Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.stream.Collectors;

public class RelativeSortArray {
    public static void main(String[] args) {
        int arr1[] = { 2, 3, 1, 3, 2, 6,7,9,2,19 };
        int arr2[] = { 2, 1, 4, 3,9,6 };
        // [22,28,8,6,17,44]
        int arr[] = relativeSortArray(arr1, arr2);
        System.out.println(Arrays.toString(arr));
    }

    public static int[] relativeSortArray(int[] arr1, int[] arr2) {
        int a[] = new int[arr1.length];
        // convert array to arraylist with sorting
        ArrayList<Integer> list1 = (ArrayList<Integer>) 
          Arrays.stream(arr1).boxed().sorted()
                .collect(Collectors.toList());
        HashMap<Integer, Integer> freq = new HashMap<>();
        // frequency count
        // iterate till end of loop
        for (int i = 0; i < arr1.length; i++) {
            // count frequency of every element
            freq.put(arr1[i], freq.getOrDefault(arr1[i], 0) + 1);
        }
        int index = 0;
        for (int i = 0; i < arr2.length; i++) {
            if (freq.containsKey(arr2[i])) {
                int vC = freq.get(arr2[i]);
                for (int j = 0; j < vC; j++) {
                    a[index++] = arr2[i];
                    list1.remove(list1.indexOf(arr2[i]));
                }
            }
        }
        // remaining element add at last
        for (int v : list1) {
            a[index++] = v;
        }
        return a;
    }

}

C++

#include <bits/stdc++.h>
using namespace std;


//function to sort the array according
//to the second array
vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) 
{
        map<int,int> mp;
        int n=arr1.size();
        for(int i=0;i<n;i++)
              mp[arr1[i]]++;
        vector<int> v;
        int m=arr2.size();
       for(int i=0;i<m;i++)
       {
           int x=mp[arr2[i]];
           while(x--)
                  v.push_back(arr2[i]);
           mp[arr2[i]]=0;
       }
        for(auto it=mp.begin();it!=mp.end();it++)
        {
            int x=it->second;
            while(x--)
                  v.push_back(it->first);
        }
        return v;
}
int main()
{
    vector<int> arr1 ={2,3,1,3,2,4,6,7,9,2,19};
    vector<int> arr2 = {2,1,4,3,9,6};
    vector<int> result=relativeSortArray(arr1,arr2);
    for(int i=0;i<result.size();i++)
       cout<<result[i]<<" ";
   return 0;
}