給定一個(gè)非空整數(shù)數(shù)組,除了某個(gè)元素只出現(xiàn)一次以外喇颁,其余每個(gè)元素均出現(xiàn)兩次漏健。找出那個(gè)只出現(xiàn)了一次的元素。
說(shuō)明:
你的算法應(yīng)該具有線性時(shí)間復(fù)雜度橘霎。 你可以不使用額外空間來(lái)實(shí)現(xiàn)嗎蔫浆?
示例 1:
輸入: [2,2,1]
輸出: 1
示例 2:
輸入: [4,1,2,1,2]
輸出: 4
方法一
func SingleNumber(nums []int) int {
// 先排序
sort.Ints(nums)
var length = len(nums)
if length == 1 {
return nums[0]
}
var count = 1
var ret = 0
//
for i := 1; i < length; i++ {
//當(dāng)前值與前一個(gè)值是不是相等,相等加一
// 不相等的話如果count =1 就是表示前一個(gè)值的個(gè)數(shù)唯一
if nums[i] == nums[i-1] {
count++
continue
}
if count == 1 {
ret = nums[i-1]
count = 0
break
}
count = 1
}
// 最后一個(gè)是單數(shù)
if count == 1 {
ret = nums[length-1]
}
return ret
}
方法二
說(shuō)明就是利用相同的值異或?yàn)榱鉧^a = 0
func SingleNumber(nums []int) int {
a := 0
for _, i := range nums {
a ^= i
}
return a
}