Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
Chào anh em, các ae có thể xem Đề bài và Solution của mình trên LeetCode nhé:
You are given two 0-indexed integer permutations A
and B
of length n
.
A prefix common array of A
and B
is an array C
such that C[i]
is equal to the count of numbers that are present at or before the index i
in both A
and B
.
Return the prefix common array of A
and B
.
A sequence of n
integers is called a permutation if it contains all integers from 1 to n
exactly once.
Example 1:
Input: A = [1,3,2,4], B = [3,1,2,4] Output: [0,2,3,4] Explanation: At i = 0: no number is common, so C[0] = 0. At i = 1: 1 and 3 are common in A and B, so C[1] = 2. At i = 2: 1, 2, and 3 are common in A and B, so C[2] = 3. At i = 3: 1, 2, 3, and 4 are common in A and B, so C[3] = 4.
Example 2:
Input: A = [2,3,1], B = [3,1,2] Output: [0,1,3] Explanation: At i = 0: no number is common, so C[0] = 0. At i = 1: only 3 is common in A and B, so C[1] = 1. At i = 2: 1, 2, and 3 are common in A and B, so C[2] = 3.
Constraints:
1 <= A.length == B.length == n <= 50
1 <= A[i], B[i] <= n
A
and B
are both a permutation of n
integers.Xin chào anh em dev thân mến! Hôm nay chúng ta sẽ "phá đảo" một bài toán cực kỳ thú vị về xử lý mảng - Finding the Prefix Common Array. Khi nhìn vào bài này, mình nghĩ ngay đến việc sử dụng frequency array để track các phần tử chung giữa hai mảng. Đây là một approach khá elegant và hiệu quả! 🤓
Mình xin chia sẻ cách tiếp cận chi tiết:
Ví dụ minh họa:
A = [1, 3, 2, 4]
B = [3, 1, 2, 4]
Cần tìm số phần tử chung tại mỗi index:
- Index 0: A[0]=1, B[0]=3 -> 0 phần tử chung
- Index 1: thêm A[1]=3, B[1]=1 -> 2 phần tử chung (1 và 3)
- Index 2: thêm A[2]=B[2]=2 -> 3 phần tử chung
- Index 3: thêm A[3]=B[3]=4 -> 4 phần tử chung
freq
để đếm tần suất xuất hiệnprefix
để lưu kết quảcnt
đếm số phần tử chungTime complexity: $O(n)$- một lần duyệt qua mảng
Space complexity: $O(k)$ - k là range của các giá trị trong mảng
class Solution {
public:
vector<int> findThePrefixCommonArray(vector<int>& A, vector<int>& B) {
int n = A.size();
// Khởi tạo mảng đếm tần suất
vector<int> freq(n + 1, 0);
vector<int> prefix(n, 0);
int cnt = 0;
// Duyệt qua từng index
for (int i = 0; i < n; i++) {
// Xử lý phần tử từ mảng A
if (++freq[A[i]] == 2) cnt++;
// Xử lý phần tử từ mảng B
if (++freq[B[i]] == 2) cnt++;
// Cập nhật kết quả
prefix[i] = cnt;
}
return prefix;
}
};
// Hàm in mảng helper
void printArray(const vector<int>& arr) {
cout << "[";
for (int i = 0; i < arr.size(); i++) {
cout << arr[i];
if (i < arr.size() - 1) cout << ", ";
}
cout << "]" << endl;
}
int main() {
Solution sol;
// Test Case 1
cout << "\n🔍 Test Case 1:" << endl;
vector<int> A1 = {1, 3, 2, 4};
vector<int> B1 = {3, 1, 2, 4};
cout << "Input:" << endl;
cout << "A = "; printArray(A1);
cout << "B = "; printArray(B1);
cout << "Output: ";
printArray(sol.findThePrefixCommonArray(A1, B1));
cout << "Expected: [0, 2, 3, 4]" << endl;
// Test Case 2
cout << "\n🔍 Test Case 2:" << endl;
vector<int> A2 = {1, 2, 3};
vector<int> B2 = {3, 2, 1};
cout << "Input:" << endl;
cout << "A = "; printArray(A2);
cout << "B = "; printArray(B2);
cout << "Output: ";
printArray(sol.findThePrefixCommonArray(A2, B2));
cout << "Expected: [0, 1, 3]" << endl;
// Test Case 3: Edge case - một phần tử
cout << "\n🔍 Test Case 3:" << endl;
vector<int> A3 = {1};
vector<int> B3 = {1};
cout << "Input:" << endl;
cout << "A = "; printArray(A3);
cout << "B = "; printArray(B3);
cout << "Output: ";
printArray(sol.findThePrefixCommonArray(A3, B3));
cout << "Expected: [1]" << endl;
// Test Case 4: Các số trùng nhau hoàn toàn
cout << "\n🔍 Test Case 4:" << endl;
vector<int> A4 = {1, 1, 1};
vector<int> B4 = {1, 1, 1};
cout << "Input:" << endl;
cout << "A = "; printArray(A4);
cout << "B = "; printArray(B4);
cout << "Output: ";
printArray(sol.findThePrefixCommonArray(A4, B4));
cout << "Expected: [1, 2, 3]" << endl;
return 0;
}
P/S: Đây là một bài trong series LeetCode Daily Challenge của mình. Anh em có thể check profile để xem các bài trước. Happy coding! 💻✨
Lại code Editor vô chi cho ae đây ......