Сложность: medium
Если задан целочисленный массив четной длины arr, верните true, если можно переупорядочить arr так, чтобы arr[2 * i + 1] = 2 * arr[2 * i] для каждого 0 <= i < len(arr) / 2, или false в противном случае.
Пример:
Input: arr = [3,1,3,6]
Output: false
👨💻 Алгоритм:
1⃣Подсчитать частоту каждого элемента в массиве.
Отсортировать массив по абсолютным значениям элементов.
2⃣Для каждого элемента в отсортированном массиве:
Проверить, можно ли сопоставить его с элементом, равным его удвоенному значению.
Уменьшить счетчик обоих элементов в словаре частот.
3⃣Если для каждого элемента можно найти пару, вернуть true, иначе вернуть false.
😎 Решение:
class Solution {
public:
bool canReorderDoubled(vector<int>& arr) {
unordered_map<int, int> count;
for (int num : arr) {
count[num]++;
}
sort(arr.begin(), arr.end(), [](int a, int b) { return abs(a) < abs(b); });
for (int num : arr) {
if (count[num] == 0) continue;
if (count[2 * num] == 0) return false;
count[num]--;
count[2 * num]--;
}
return true;
}
};Ставь 👍 и забирай 📚 Базу знаний