Nay rảnh ngồi làm mấy bài leetcode, thấy bài này khá hay, nên muốn share lại:
https://leetcode.com/problems/array-of-doubled-pairs/
Input của bài này là 1 dãy có số phần tử là số chẵn. Yêu cầu cần xác định xem mảng đó có thể đc sắp xếp lại để các phần tử trong mảng đi với nhau từng cặp, và số phía sau gấp đôi số phía trước:
vd: [1,2,2,1] -> reorder lại thành [1,2,1,2] -> true
vd: [1,2,2,1,4,1] -> có 3 số 1 mà chỉ có 1 số 2 nên k đủ để bắt cặp cho số 1 -> false
vd: [1,2,2,2,4,1] -> reorder lại thành [1,2,1,2,2,4] -> true
Để giải quyết bài này thì cách đầu tiên mình nghĩ đến là đơn giản duyệt hết các phần tử trong mảng, sau đó search xem có tồn tại phần tử để ghép cặp không bằng cách x2 (và /2 nếu số đó là số chẵn). Tuy nhiên nó sẽ có 1 vấn đề như vd dưới đây:
[4,8,2,16] : khi duyệt đến 4 thì mình lấy 8 để ghép thành 1 cặp, còn lại 2,16 thì không ghép được -> false. Trong khi dãy nãy hoàn toàn có thể được reorder như sau để thỏa mãn yêu cầu của bài toán: [2,4,8,16].
=> mình cần phải sort trước khi duyệt. Cộng với yêu cầu về search nên bài này rất phù hợp để dùng map.
C++:
class Solution {
public:
bool canReorderDoubled(vector<int>& arr) {
map<int,int> myMap;
for (auto x : arr){
myMap[x]++;
}
for (auto it : myMap){
if (it.first == 0 || it.second <= 0) continue;
auto find_it = it.first > 0 ? myMap.find(it.first*2) : it.first%2==0 ? myMap.find(it.first/2) : myMap.end();
if (find_it == myMap.end() || find_it->second < it.second) return false;
find_it->second -= it.second;
}
return true;
}
};
Runtime: 72 ms, faster than 95.72% of C++ online submissions for Array of Doubled Pairs.
Memory Usage: 58 MB, less than 53.38% of C++ online submissions for Array of Doubled Pairs.
Độ phức tạp của solution này là O(NlogN).
