Sword finger offer II 075 Array relative sort (custom sort, count sort)

The finger of the sword Offer II 075. Array relative sort （ Custom sort 、 Count sorting ）

Title Description

Method 1 ： The simplest and easiest way to think of

• Use one map<int, int> mp Record arr1 The number of occurrences of each number in
• Traverse arr2 At the same time , To the answer array ans Add... In the loop arr2[i], The number of cycles is arr1 Is the number of times , With a variable at the same time cnt Record the sum of all occurrences . namely mp[arr2[i]], At the end of traversal arr1 Appears in arr2 The numbers in are in order
• Use one set<int> st Storage arr2 Number in , Traverse arr1, If it doesn't appear in st in , Just add it to the answer array ans Back ;
• Come here ,ans The first... In the array cnt The numbers are already in order , The following numbers are out of order , Just sort the following numbers sort(ans.begin() + cnt, ans.end()).

class Solution {
    
public:
    vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
    
        map<int, int> mp;
        set<int> st;
        for (int i = 0; i < arr1.size(); i++) {
    
            mp[arr1[i]]++;
        }
        vector<int> tmp;
        int cnt = 0;
        for (auto k : arr2) {
    
            st.insert(k);
            int n = mp[k];
            cnt += n;
            while (n--) {
    
                tmp.push_back(k);
            }
        }
        for (auto num : arr1) {
    
            if (st.find(num) == st.end()) {
    
                tmp.push_back(num);
            }
        }
        sort(tmp.begin() + cnt, tmp.end());
        return tmp;
    }
};

Method 2 ： Directly customize the sorting of arrays

After reading the solution , To sum up . In fact, you can customize the sorting method , Yes arr1 Sort directly .

• Start with a hash table map<int, int> mp Record arr2 All numbers in arr2[i] And its subscript position [i], That is to say mp[arr2[i]] = [i];
• Customize sort Comparison method in function , For two elements a、b：
  • If a、b All in the hash table , explain a、b All in arr2 in , So compare their subscript positions , Elements with small subscripts are smaller ;
  • If a、b Are not in the hash table , Compare in normal size order ;
  • If one is in a hash table , One is not in the hash table , Then the elements in the hash table are smaller .
• Direct pair arr1 Just sort it out .
• Time complexity ：$O(nlogn)$ Spatial complexity ：$O(m)$

class Solution {
    
public:
    vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
    
        unordered_map<int, int> mp;
        for (int i = 0; i < arr2.size(); i++) {
    
            mp[arr2[i]] = i;
        }
        sort(arr1.begin(), arr1.end(), [&](const int &a, const int &b) {
    
            if (mp.count(a)) {
    
                return mp.count(b) ? mp[a] < mp[b] : true;
            } else {
    
                return mp.count(b) ? false : a < b;
            }
        });
        return arr1;
    }
};

Method 3 ： Count sorting （ Optimize method 1 ）

Consider method one carefully , In fact, it is a bit like counting and sorting . Sort by count , There is no need to use a hash table to store the number of occurrences of an element , Instead, use an array . Topic arr2 The maximum value of elements in the array does not exceed 1000, So you can open a length of 1001 Array to record each number in arr1 Is the number of times , as well as arr2 The elements that appear in .

• Time complexity $O(n+m+1001)$, Spatial complexity $O(1001)$

class Solution {
    
public:
    vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
    
        vector<int> freq(1001);
        for (auto num : arr1) {
    
            freq[num]++;
        }
        vector<int> ans;
        for (auto num : arr2) {
    
            while (freq[num]) {
    
                ans.push_back(num);
                freq[num]--;
            }
        }
        for (int i = 0; i < freq.size(); i++) {
    
            while (freq[i]) {
    
                ans.push_back(i);
                freq[i]--;
            }
        }
        return ans;
    }
};