diff options
author | Jack Sangdahl <[email protected]> | 2025-01-13 19:50:52 -0700 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-01-13 19:50:52 -0700 |
commit | b7b7dd2713396b261a1ffd8be1c330c2fd828f9d (patch) | |
tree | ccd547cb212151b164d41334b8d3406fffa28b92 | |
parent | 32b3c8cc7a72294298aabcedc2033b06f2a7ca5e (diff) | |
download | leetcode-b7b7dd2713396b261a1ffd8be1c330c2fd828f9d.tar.gz leetcode-b7b7dd2713396b261a1ffd8be1c330c2fd828f9d.zip |
2657. find the prefix common array of the two arrays
-rw-r--r-- | find_prefix_common_arr.c | 43 | ||||
-rw-r--r-- | find_prefix_common_arr.py | 33 |
2 files changed, 76 insertions, 0 deletions
diff --git a/find_prefix_common_arr.c b/find_prefix_common_arr.c new file mode 100644 index 0000000..4e5fe05 --- /dev/null +++ b/find_prefix_common_arr.c @@ -0,0 +1,43 @@ +// 2657. Find the Prefix Common Array of Two Arrays +#include "leetcode.h" + +/* + * 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. + */ + +int *findThePrefixCommonArray(int *A, int ASize, int *B, int BSize, + int *returnSize) { + int *ans = (int *)malloc(ASize * sizeof(int)), cnt = 0; + int *vis = (int *)malloc((ASize + 1) * sizeof(int)); + for (int i = 0; i < ASize; i++) { + if (++vis[A[i]] == 2) + cnt++; + if (++vis[B[i]] == 2) + cnt++; + ans[i] = cnt; + } + free(vis); + *returnSize = ASize; + return ans; +} + +int main() { + int a1[] = {1, 2, 3, 4}, b1[] = {3, 1, 2, 4}, rs1; + int a2[] = {2, 3, 1}, b2[] = {3, 1, 2}, rs2; + int *ftpca1 = + findThePrefixCommonArray(a1, ARRAY_SIZE(a1), b1, ARRAY_SIZE(b1), &rs1); + int *ftpca2 = + findThePrefixCommonArray(a2, ARRAY_SIZE(a2), b2, ARRAY_SIZE(b2), &rs2); + for (int i = 0; i < rs1; i++) + printf("%d ", ftpca1[i]); // expect: 0 2 3 4 + printf("\n"); + for (int i = 0; i < rs2; i++) + printf("%d ", ftpca2[i]); // expect: 0 1 3 + printf("\n"); + free(ftpca1), free(ftpca2); +} diff --git a/find_prefix_common_arr.py b/find_prefix_common_arr.py new file mode 100644 index 0000000..ccce100 --- /dev/null +++ b/find_prefix_common_arr.py @@ -0,0 +1,33 @@ +# 2657. Find the Prefix Common Array of Two Arrays + +""" +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. +""" + + +class Solution(object): + def findThePrefixCommonArray(self, A, B): + """ + :type A: List[int] + :type B: List[int] + :rtype: List[int] + """ + ans, vis, cnt = [], 0, 0 + for ab in zip(A, B): + for a in ab: + if (1 << a) & vis: + cnt += 1 + vis |= 1 << a + ans.append(cnt) + return ans + + +if __name__ == "__main__": + obj = Solution() + print(obj.findThePrefixCommonArray(A=[1, 3, 2, 4], B=[3, 1, 2, 4])) + print(obj.findThePrefixCommonArray(A=[2, 3, 1], B=[3, 1, 2])) |