-
-
Notifications
You must be signed in to change notification settings - Fork 9.5k
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
【每日一题】- 2019-08-26 - 1122. 数组的相对排序 #145
Labels
Comments
|
static vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
auto m = unordered_map<int, int>();
for (auto i = 0; i < arr2.size(); ++i) {
m[arr2[i]] = i;
}
for (auto v : arr1) {
if (m.find(v) == m.end()) {
m[v] = 1000 + v;
}
}
sort(arr1.begin(), arr1.end(), [&m](int a, int b) {
return m[a] < m[b];
});
return arr1;
} |
python3 class Solution:
def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:
d2 = {}
for num,i in enumerate(arr2):
d2[i] = num
# print(d2)
d1 = {}
rest = []
for i in arr1:
if i in d2:
if d2[i] not in d1:
d1[d2[i]] = [i,0]
d1[d2[i]][1] += 1
else:
rest.append(i)
# print(d1)
res = []
for i in sorted(d1):
for _ in range(d1[i][1]):
res.append(d1[i][0])
return res + sorted(rest) |
【c++】【STL】 class Solution {
public:
vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
map<int,int> mp;
unordered_map<int,bool> st;
vector<int> res;
for(int i = 0;i<arr1.size();i++) mp[arr1[i]]++;
for(int i = 0;i<arr2.size();i++) st[arr2[i]] = true;
for(int i = 0;i<arr2.size();i++){
while(mp[arr2[i]]--){
res.push_back(arr2[i]);
}
}
for(auto &m:mp){
if(!st[m.first]){
while(mp[m.first]--){
res.push_back(m.first);
}
}
}
return res;
}
}; |
看了上面这位兄弟的思路,感觉思路非常好,在此贴一下自己的cpp版本代码 class Solution {
public:
unordered_map<int,int> mp;
vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
for(int i = 0;i<arr2.size();i++) mp[arr2[i]] = i+1;
for(int i = 0;i<arr1.size();i++) if(!mp[arr1[i]]) mp[arr1[i]] = arr1[i]+2000;
sort(arr1.begin(),arr1.end(),[&](int &a,int &b){return mp[a]<mp[b];});
return arr1;
}
}; |
This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions. |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
给你两个数组,arr1 和 arr2,
arr2 中的元素各不相同
arr2 中的每个元素都出现在 arr1 中
对 arr1 中的元素进行排序,使 arr1 中项的相对顺序和 arr2 中的相对顺序相同。未在 arr2 中出现过的元素需要按照升序放在 arr1 的末尾。
示例:
输入:arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]
输出:[2,2,2,1,4,3,3,9,6,7,19]
提示:
arr1.length, arr2.length <= 1000
0 <= arr1[i], arr2[i] <= 1000
arr2 中的元素 arr2[i] 各不相同
arr2 中的每个元素 arr2[i] 都出现在 arr1 中
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/relative-sort-array
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
The text was updated successfully, but these errors were encountered: