一个整型数组里除了两个数字之外，其他的数字都出现了两次

问题描述：

一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

示例：

输入： [1, 1, 7, 2, 5, 6, 6, 7]

输出: 2, 5

解题思路：利用异或来求解

异或知识：

1. 两个相同的数据求异或后位0， a ^ a = 0

2. 交换两个整数的值可以使用异或实现 a=a^b; b=b^a;a=a^b

本题思路是可以利用异或求出一个出现一次的数据，可以将两个数据分开去求解，所以重点是如何区分两个出现单个的数值，并对数组进行分组。通过对两个数据求异或转为二进制，然后判断出现1的最近的位置，将列表中的数据二进制形态的该位置的数据与0x01求同或，为1的分一组，为0的分一组，即两个单次出现的值分别出现在两个数据中，对出现在两个数组中的数据求异或，即可求出单次出现的数组。

package main

import(
	"fmt"
)

func findDiffNum(arr []int) (int, int) {
	a := 0
	for _, v := range arr {
		a = a ^ v
	}

	pos := 0 
	for a & 0x01 != 1 {
		pos++
		a = a >> 1
	}

	num1, num2 := 0, 0
	for _, v := range arr {
		if v >> pos & 0x01 == 0 {
			num1 = num1 ^ v 
		} else {
			num2 = num2 ^ v 
		}
	}

	return num1, num2
}

func main()  {
	fmt.Println(findDiffNum([]int{1, 1, 7, 2, 5, 6, 6, 7}))
}

最后

以上就是温婉星星为你收集整理的一个整型数组里除了两个数字之外，其他的数字都出现了两次的全部内容，希望文章能够帮你解决一个整型数组里除了两个数字之外，其他的数字都出现了两次所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。