1122. Relative Sort Array
描述：给一个待排序的数组A，以及一个位置打打乱的参考数组B。 如果A的某一个元素在B中，就需要按照B数组的先后顺序进行排序。 如果A的某一个元素不在B中，则需要放在最后面，同时按照大小顺序排序。 思路：map计数即可，然后先原B数组整有的元素依次放入答案容器，最后遍历map将剩下的元素放入答案。 提示：map的key是按升序排列的。 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]
（1,2是一类，3,4是一类）
- my solution：(4 ms, 8.7 MB)
int i, j, count = 0; vector<int> output1; for (i = 0; i<arr2.size(); i++) for (j = 0; j<arr1.size(); j++){ if (arr1[j] == arr2[i]){ output1.push_back(arr2[i]); arr1.erase(arr1.begin() + j); j--; } } sort(arr1.begin(), arr1.end()); output1.insert(output1.end(), arr1.begin(), arr1.end()); return output1; - 利用swap（8 ms, 8.8 MB）
int index = 0; for (int i = 0; i < arr2.size(); ++i) { for (int j = index; j < arr1.size(); ++j) { if (arr2[i] == arr1[j]) // find element in arr2 { swap(arr1[j], arr1[index]); // put it at right place index++; } } } // sort rest elements sort(arr1.begin() + index, arr1.end()); return arr1; - 动态规划(0 ms, 8.8 MB)
vector<int> dp(1001,0); //0 <= arr1[i], arr2[i] <= 1000，dp的索引存储的是arr的值，dp[i]是值为i的次数。 vector<int> res; for(int i=0;i<arr1.size();i++) // 保存arr1的每个元素的频数 dp[arr1[i]]++; for(int i=0;i<arr2.size();i++) { for(int j=0;j<dp[arr2[i]];j++) // 保存dp[arr2[i]]个元素arr2[i]（重复的元素）到res res.push_back(arr2[i]); dp[arr2[i]]=0; // arr2中元素对应的频数置为0 } for(int i=0;i<=1000;i++) for(int j=0;j<dp[i];j++) res.push_back(i); //升序保存arr1元素到res return res; - map(8 ms，9.1 MB)
class Solution { public: vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) { map<int,int> M; vector<int> ans; for(auto v1: arr1) M[v1]++; for(auto v2: arr2) { while(M[v2]) { ans.push_back(v2); M[v2]--; } } for(auto m: M) { while(m.second) { ans.push_back(m.first); m.second--; } } return ans; } };
