🔒Открыть пост
и посмотреть медиа
и посмотреть медиа
Задача: 870. Advantage Shuffle
Сложность: medium
Даны два целочисленных массива nums1 и nums2 одинаковой длины. Преимущество nums1 относительно nums2 — это количество индексов i, для которых nums1[i] > nums2[i].
Верните любую перестановку nums1, которая максимизирует его преимущество относительно nums2.
Пример:
Input: nums1 = [2,7,11,15], nums2 = [1,10,4,11]
Output: [2,11,7,15]
👨💻 Алгоритм:
1⃣Отсортируйте nums1 и nums2. Для каждой карты a из отсортированного nums1 определите, может ли она побить текущую наименьшую карту b из отсортированного nums2. Если да, добавьте a в assigned[b], если нет, добавьте a в remaining.
2⃣После распределения всех карт из nums1, используйте assigned и remaining для построения итогового результата. Для каждой карты b из nums2, если assigned[b] не пуст, добавьте в результат последнюю карту из assigned[b], иначе добавьте последнюю карту из remaining.
3⃣Верните итоговый результат.
😎 Решение:
class Solution {
public:
vector advantageCount(vector& A, vector& B) {
vector sortedA(A);
sort(sortedA.begin(), sortedA.end());
vector sortedB;
for (int i = 0; i < B.size(); ++i)
sortedB.push_back({B[i], i});
sort(sortedB.begin(), sortedB.end());
unordered_map assigned;
for (int b: B) assigned[b] = {};
deque remaining;
int j = 0;
for (int a: sortedA) {
if (a > sortedB[j].first) {
assigned[sortedB[j++].first].push_back(a);
} else {
remaining.push_back(a);
}
}
vector ans(B.size());
for (int i = 0; i < B.size(); ++i) {
if (assigned[B[i]].size() > 0) {
ans[i] = assigned[B[i]].front();
assigned[B[i]].pop_front();
} else {
ans[i] = remaining.front();
remaining.pop_front();
}
}
return ans;
}
};
Ставь 👍 и забирай 📚 Базу знаний
