LeetCode 2657. Find the Prefix Common Array of Two Arrays 由於數值範圍不大，可以利用程式語言中，找出 Set Intersection 數量的方法。
C++ 就用 bitset
class Solution {
public:
vector<int> findThePrefixCommonArray(vector<int>& A, vector<int>& B) {
const int n = A.size();
bitset<51> aSet, bSet;
vector<int> ans(n);
for (int i = 0; i < n; ++i) {
aSet[A[i]] = true;
bSet[B[i]] = true;
bitset<51> cSet = aSet & bSet;
ans[i] = cSet.count();
}
return ans;
}
};
Python3 就用 set
class Solution:
def findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:
n = len(A)
aSet = set()
bSet = set()
arr = []
for i in range(n):
aSet.add(A[i])
bSet.add(B[i])
arr.append(len(aSet & bSet))
return arr
Go 沒有內建的 Set Intersection 方法，所以就另外處理。
func findThePrefixCommonArray(A []int, B []int) []int {
n := len(A)
arr := make([]int, n)
seen := make([]int, n+1)
commonCount := 0
for i := 0; i < n; i++ {
seen[A[i]]++
if seen[A[i]] == 2 {
commonCount++
}
seen[B[i]]++
if seen[B[i]] == 2 {
commonCount++
}
arr[i] = commonCount
}
return arr
}
最後是 Rust 可以用 u64
impl Solution {
pub fn find_the_prefix_common_array(a: Vec<i32>, b: Vec<i32>) -> Vec<i32> {
let mut aSet: u64 = 0;
let mut bSet: u64 = 0;
let n = a.len();
let mut arr = Vec::with_capacity(n);
for i in 0..n {
aSet |= 1 << a[i];
bSet |= 1 << b[i];
arr.push((aSet&bSet).count_ones() as i32);
}
arr
}
}
考慮到可讀性跟效能大概可以這樣寫，不然就要去用 popcount 還是 __builtin_popcount 就先略過。
