集合的交集數量

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 就先略過。