2020-06-22：已知两个非负数的异或值为M，两数之和为N，求这两个数？
【摘要】 福哥答案2020-06-22：1.遍历法时间复杂度：O(N)最好空间复杂度：O(1)平均空间复杂度：O(sqrt(N))最坏空间复杂度：O(N)[0,N/2]依次遍历，符合条件的就是需要的结果。2.位运算法最好时间复杂度：O(1)平均时间复杂度：O(sqrt(N))最坏时间复杂度：O(N)最好空间复杂度：O(1)平均空间复杂度：O(sqrt(N))最坏空间复杂度：O(N)1100100 两数...
福哥答案2020-06-22：
1.遍历法
时间复杂度：O(N)
最好空间复杂度：O(1)
平均空间复杂度：O(sqrt(N))
最坏空间复杂度：O(N)
[0,N/2]依次遍历，符合条件的就是需要的结果。
2.位运算法
最好时间复杂度：O(1)
平均时间复杂度：O(sqrt(N))
最坏时间复杂度：O(N)
最好空间复杂度：O(1)
平均空间复杂度：O(sqrt(N))
最坏空间复杂度：O(N)
1100100 两数和N=100，已知
0010100 异或值M=20，已知
1010000 差N-M=80，如果差为负数或者差为奇数，直接返回空
0101000 差右移1位。
0010100 异或值M=20，已知
0101000 差右移1位。
将上面两个二进制数换成中文如下：
同同异同异同同
零幺零幺零零零
零幺异幺异零零=01x1x00，x代表0和1，只要满足这样的数就行。规则：同零=0，同幺=1，异零=x，异幺=不符合条件。只要出现了异幺，直接返回空。
golang代码如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
|
package
test23_xorandsum
import
(
"fmt"
"testing"
)
const
(
SameOne =
1
SameZero =
0
Different =
2
DifferentZero =
0
)
//go test -v -test.run TestXorAndSum
func TestXorAndSum(t *testing.T) {
//M := uint(20)
//N := uint(100)
M := uint(
1
)
N := uint(
9
)
fmt.Println(
"M = "
, M)
fmt.Println(
"N = "
, N)
fmt.Println(
"遍历法："
, xorAndSum1(M, N))
fmt.Println(
"位操作法："
, xorAndSum2(M, N))
}
//M是两个数异或值
//N是两个数之和
//1.遍历法
func xorAndSum1(M uint, N uint) [][]uint {
ret := make([][]uint,
0
)
//返回多个值
n := N >>
1
//只需要遍历一半
temp := uint(
0
)
for
i := uint(
0
); i <= n; i++ {
temp = M ^ i
if
N-i == temp {
//找到异或值和两数和的两个数了
ret = append(ret, []uint{i, temp})
}
}
return
ret
}
//M是两个数异或值
//N是两个数之和
//2.位操作法
func xorAndSum2(M uint, N uint) [][]uint {
ret := make([][]uint,
0
)
//返回多个值
//两数之和小于两数异或值，不存在这样的情况
if
N < M {
return
ret
}
sub := N - M
//差值
//不能被2整除，不存在这样的情况
if
sub&
1
==
1
{
return
ret
}
//生成中间结果
sub >>=
1
//差值右移动一位，方便做判断
slicebit := make([]
byte
,
0
)
kind := uint(
1
)
for
sub >
0
|| M >
0
{
if
M&
1
==
1
{
//当前位，两数不同
if
sub&
1
==
1
{
//不存在这样的情况
return
ret
}
else
{
slicebit = append(slicebit, Different)
kind <<=
1
}
}
else
{
//当前位，两数相同
if
sub&
1
==
1
{
//当前位肯定都为1
slicebit = append(slicebit, SameOne)
}
else
{
//当前位肯定都为0
slicebit = append(slicebit, SameZero)
}
}
sub >>=
1
M >>=
1
}
//两数异或值M第1个1位0，作用是去重
for
i := len(slicebit) -
1
; i >=
0
; i-- {
if
slicebit[i] == Different {
slicebit[i] = DifferentZero
kind >>=
1
break
}
}
//生成结果
retsingle := uint(
0
)
tempi1 := uint(
0
)
tempi2 := uint(
0
)
for
i := uint(
0
); i < kind; i++ {
//遍历种类
retsingle =
0
tempi1 = i
//这段代码可以省略，影响打印顺序
//00=0 01=1 10=2 11=3
//00=0 10=2 01=1 11=3
kindtemp := kind
tempi2 =
0
for
{
tempi2 <<=
1
tempi2 |= tempi1 &
1
tempi1 >>=
1
kindtemp >>=
1
if
kindtemp <=
1
{
break
}
}
tempi1 = tempi2
//生成结果
for
j := len(slicebit) -
1
; j >=
0
; j-- {
retsingle <<=
1
if
slicebit[j] <= SameOne {
retsingle |= uint(slicebit[j])
}
else
{
retsingle |= uint(tempi1 &
1
)
tempi1 >>=
1
}
}
//将结果保存起来
ret = append(ret, []uint{retsingle, N - retsingle})
}
return
ret
}
|
敲命令go test -v -test.run TestXorAndSum，执行结果如下：
【版权声明】本文为华为云社区用户原创内容，转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息， 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）