数组中只出现一次的两个数字
About 4 min
数组中只出现一次的两个数字
题目链接
题目描述
一个整型数组里除了两个数字只出现一次,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
数据范围:数组长度 2≤n≤1000,数组中每个数的大小 0<val≤1000000 要求:空间复杂度O(1),时间复杂度O(n)
提示:输出时按非降序排列。
示例:
#输入:
[1,4,1,6]
#返回值:
[4,6]
#说明:
#返回的结果中较小的数排在前面
刷题思路
方案一:
- 对数组进行排序(升序)
- 按照
在开头
、在中间
、在结尾
,三种情况分条件比较
有点投机取巧,可以使用sort进行排序,也可以使用时间复杂度最低的快速排序
方案二:
- 利用哈希表,统计出现次数
- 遍历哈希表,找出只出现一次的,升序输出
方案三:
- 利用位运算,即:异或运算(同0异1)
异或运算不常用,有点难度
代码实现
/**
* 先排序,利用出现一次特性
*/
function findNumsAppearOnceOne(array) {
// 数组中元素要么出现一次,要么出现两次,可以先对元素进行排序有点偷懒的样子
array = array.sort((a, b) => a - b)
const len = array.length
// 此时的 数组已经进过排序
const onceResult = []
// 在开头
if (array[0] !== array[1]) {
onceResult.push(array[0])
}
// 在中间
for (let index = 1; index < len - 1; index++) {
if (array[index - 1] !== array[index] && array[index] !== array[index + 1]) {
onceResult.push(array[index])
}
}
// 在结尾
if (array[array.length - 1] !== array[array.length - 2]) {
onceResult.push(array[array.length - 1])
}
return onceResult
}
/**
* 利用Map统计出现次数
*/
function findNumsAppearOnceTwo(array) {
const resMap = new Map()
// 统计
for (const value of array) {
if (resMap.has(value)) {
resMap.set(value, resMap.get(value) + 1)
}
else {
resMap.set(value, 1)
}
}
const onceResult = []
// 找出出现一次的
for (const [key, value] of resMap) {
if (value === 1) {
onceResult.push(key)
}
}
// 按从小到大输出
return onceResult.sort((a, b) => a - b)
}
/**
* 利用异或运算
*/
function findNumsAppearOnceThree(array) {
let res1 = 0
let res2 = 0
let temp = 0
// 遍历数组得到a^b
for (let i = 0; i < array.length; i++) {
temp ^= array[i]
}
let k = 1
// 找到两个数不相同的第一位
while ((k & temp) === 0) {
k <<= 1
}
for (let i = 0; i < array.length; i++) {
// 遍历数组,对每个数分类
if ((k & array[i]) === 0) {
res1 ^= array[i]
}
else { res2 ^= array[i] }
}
// 升序
return res1 > res2 ? [res2, res1] : [res1, res2]
}
console.log(findNumsAppearOnceOne([1, 2, 3, 3, 2, 9]))
console.log(findNumsAppearOnceTwo([1, 2, 3, 3, 2, 9]))
console.log(findNumsAppearOnceThree([1, 2, 3, 3, 2, 9]))
一些建议
- 熟练使用基本数组排序
Map
结构重要,常用api需要熟悉- 位运算是数学问题,可以了解