两个整形无序数组,数据大小[0-9],数组内元素不重复,尽量快地找出两个数组中相同元素的个数。
相亲、旅游问题抽象
例子:
[2,6,9,3,1]与[3,2,4,6],相同元素个数为3
[3,1,5,2,4,9,8]与[6,2,7],相同元素个数为1
思路:
因为数据大小为0-9,数组元素不重复,所以可以先把两个数组转成二进制数字,然后再对比两个数据相同1的个数
伪代码:
let arrayA:[Int] = [2,6,9,3,1]
let arrayB:[Int] = [3,2,4,6]
// 计算A数组的二进制
var resultBinA: Int64 = 0
for item: Int in arrayA {
resultBinA = resultBinA | (1 << item)
}
// 计算A数组的二进制
var resultBinB: Int64 = 0
for item: Int in arrayB {
resultBinB = resultBinB | (1 << item)
}
// 计算相同1个数
let compareResult: Int64 = resultBinB & resultBinA
let compareString: String = String(compareResult, radix:2)
let onlyOneString = compareString.replacingOccurrences(of: "0", with: "")
Alert(onlyOneString.count)