分享
【Leetcode】:Single Number III问题 in Go语言
u013564276 · · 1863 次点击 · · 开始浏览这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。
Given an array of numbers nums, in which exactly two elements appear only once and all
the other elements appear exactly twice. Find the two elements that appear only once.
For example:
Given nums = [1, 2, 1, 3, 2, 5], return [3,
5].
Note:
- The order of the result is not important. So in the above example,
[5, 3]is also correct.
- Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?
题目的大意是:给定一个数组,数组中的数除了两个互不相同的数外,其余数两两成对出现,现在要找出这两个数
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------
这道题拿在手上没什么简单的思路,参考了别人的结果"http://www.jianshu.com/p/402622b8ad43"
简要说下解题的思路,首先对所有数进行异或运算,那么相同的就会抵消掉,得到的结果就是两个相异的数a和b的异或,这个结果当作diff
然后求 (-diff & diff) 这个式子能得到二进制中只有一个1的数,这个1的位置代表着在这个位置上,a和b是不同的,那么就可以按照这个不同,
将所有数分为两组,第一组是该位置上与a相同,第二组是该位置上与b相同。
func singleNumber(nums []int) []int {
diff := 0
for _, v := range nums {
diff = diff ^ v
}
//得到的diff表示两个不同的数的按位异或的结果
diff = -diff & diff
result := make([]int, 2)
for _, v := range nums {
if diff & v == 0 {
result[0] = result[0] ^ v
} else {
result[1] = result[1] ^ v
}
}
return result
}有疑问加站长微信联系(非本文作者)
入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889
关注微信1863 次点击
上一篇:Go编程
下一篇:Go语言学习一 :基础语句
添加一条新回复
(您需要 后才能回复 没有账号 ?)
- 请尽量让自己的回复能够对别人有帮助
- 支持 Markdown 格式, **粗体**、~~删除线~~、
`单行代码` - 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
- 图片支持拖拽、截图粘贴等方式上传
收入到我管理的专栏 新建专栏
Given an array of numbers nums, in which exactly two elements appear only once and all
the other elements appear exactly twice. Find the two elements that appear only once.
For example:
Given nums = [1, 2, 1, 3, 2, 5], return [3,
5].
Note:
- The order of the result is not important. So in the above example,
[5, 3]is also correct.
- Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?
题目的大意是:给定一个数组,数组中的数除了两个互不相同的数外,其余数两两成对出现,现在要找出这两个数
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------
这道题拿在手上没什么简单的思路,参考了别人的结果"http://www.jianshu.com/p/402622b8ad43"
简要说下解题的思路,首先对所有数进行异或运算,那么相同的就会抵消掉,得到的结果就是两个相异的数a和b的异或,这个结果当作diff
然后求 (-diff & diff) 这个式子能得到二进制中只有一个1的数,这个1的位置代表着在这个位置上,a和b是不同的,那么就可以按照这个不同,
将所有数分为两组,第一组是该位置上与a相同,第二组是该位置上与b相同。
func singleNumber(nums []int) []int {
diff := 0
for _, v := range nums {
diff = diff ^ v
}
//得到的diff表示两个不同的数的按位异或的结果
diff = -diff & diff
result := make([]int, 2)
for _, v := range nums {
if diff & v == 0 {
result[0] = result[0] ^ v
} else {
result[1] = result[1] ^ v
}
}
return result
}