北京知名网站建设公司,电商网站开发要多少钱,网站设计项目明细,潍坊建设公司给你两个下标从 0 开始长度为 n 的整数排列 A 和 B 。
A 和 B 的 前缀公共数组 定义为数组 C #xff0c;其中 C[i] 是数组 A 和 B 到下标为 i 之前公共元素的数目。
请你返回 A 和 B 的 前缀公共数组 。
如果一个长度为 n 的数组包含 1 到 n 的元素恰好一次#xff0c;我…给你两个下标从 0 开始长度为 n 的整数排列 A 和 B 。
A 和 B 的 前缀公共数组 定义为数组 C 其中 C[i] 是数组 A 和 B 到下标为 i 之前公共元素的数目。
请你返回 A 和 B 的 前缀公共数组 。
如果一个长度为 n 的数组包含 1 到 n 的元素恰好一次我们称这个数组是一个长度为 n 的 排列 。
示例 1
输入A [1,3,2,4], B [3,1,2,4] 输出[0,2,3,4] 解释i 0没有公共元素所以 C[0] 0 。 i 11 和 3 是两个数组的前缀公共元素所以 C[1] 2 。 i 212 和 3 是两个数组的前缀公共元素所以 C[2] 3 。 i 3123 和 4 是两个数组的前缀公共元素所以 C[3] 4 。 示例 2
输入A [2,3,1], B [3,1,2] 输出[0,1,3] 解释i 0没有公共元素所以 C[0] 0 。 i 1只有 3 是公共元素所以 C[1] 1 。 i 212 和 3 是两个数组的前缀公共元素所以 C[2] 3 。
提示
1 A.length B.length n 50 1 A[i], B[i] n 题目保证 A 和 B 两个数组都是 n 个元素的排列。
法一直接模拟即可
func findThePrefixCommonArray(A []int, B []int) []int {// 用int64来记录数组A和B中出现过的数字因为最多只有50种数字// 位运算用无符号数iA : uint64(0)iB : uint64(0)n : len(A)C : []int{}for i : 0; i n; i {iA | 1 A[i]iB | 1 B[i]C append(C, getCommonBitNum(iA, iB))}return C
}func getCommonBitNum(iA, iB uint64) int {and : iA iBans : 0for and ! 0 {ansand (and - 1)}return ans
}此算法时间复杂度为O(n)空间复杂度为O(1)。
法二在计算一个数字的位数时可以用bits.OnesCount
func findThePrefixCommonArray(A []int, B []int) []int {iA : uint(0)iB : uint(0)n : len(A)// 我们已知C的大小就不初始化为空了就像c vectorC : make([]int, n)for i : 0; i n; i {iA | 1 A[i]iB | 1 B[i]C[i] bits.OnesCount(iA iB)}return C
}此算法时间复杂度为O(n)空间复杂度为O(1)。
