题目描述
下一个数。给定一个正整数，找出与其二进制表达式中1的个数相同且大小最接近的那两个数（一个略大，一个略小）。
示例1:
输入：num = 2（或者0b10）
输出：[4, 1] 或者（[0b100, 0b1]）
示例2:
输入：num = 1
输出：[2, -1]
提示:
num的范围在[1, 2147483647]之间；- 如果找不到前一个或者后一个满足条件的正数，那么输出 -1。
解法
方法一：位运算
我们先考虑如何找出第一个比 $num$ 大且二进制表示中 $1$ 的个数相同的数。
我们可以从低位到高位遍历 $num$ 的相邻两个二进制位，如果低位为 $1$，且相邻的较高一位为 $0$，那么我们就找到了一个位置，我们可以将这个位置的 $0$ 变成 $1$，将这个位置的 $1$ 变成 $0$。然后我们把其余低位的 $1$ 全部移动到最低位，这样我们就得到了一个比 $num$ 大且二进制表示中 $1$ 的个数相同的数。
同理，我们可以找到第一个比 $num$ 小且二进制表示中 $1$ 的个数相同的数。
我们可以从低位到高位遍历 $num$ 的相邻两个二进制位，如果低位为 $0$，且相邻的较高一位为 $1$，那么我们就找到了一个位置，我们可以将这个位置的 $1$ 变成 $0$，将这个位置的 $0$ 变成 $1$。然后我们把其余低位的 $0$ 全部移动到最低位，这样我们就得到了一个比 $num$ 小且二进制表示中 $1$ 的个数相同的数。
在实现上，我们可以用一段代码来统一处理以上两种情况。
时间复杂度 $O(\log n)$，其中 $n$ 是 $num$ 的大小。空间复杂度 $O(1)$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 | class Solution:
def findClosedNumbers(self, num: int) -> List[int]:
ans = [-1] * 2
dirs = (0, 1, 0)
for p in range(2):
a, b = dirs[p], dirs[p + 1]
x = num
for i in range(1, 31):
if (x >> i & 1) == a and (x >> (i - 1) & 1) == b:
x ^= 1 << i
x ^= 1 << (i - 1)
j, k = 0, i - 2
while j < k:
while j < k and (x >> j & 1) == b:
j += 1
while j < k and (x >> k & 1) == a:
k -= 1
if j < k:
x ^= 1 << j
x ^= 1 << k
ans[p] = x
break
return ans
|
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 | class Solution {
public int[] findClosedNumbers(int num) {
int[] ans = {-1, -1};
int[] dirs = {0, 1, 0};
for (int p = 0; p < 2; ++p) {
int a = dirs[p], b = dirs[p + 1];
int x = num;
for (int i = 1; i < 31; ++i) {
if ((x >> i & 1) == a && (x >> (i - 1) & 1) == b) {
x ^= 1 << i;
x ^= 1 << (i - 1);
int j = 0, k = i - 2;
while (j < k) {
while (j < k && (x >> j & 1) == b) {
++j;
}
while (j < k && (x >> k & 1) == a) {
--k;
}
if (j < k) {
x ^= 1 << j;
x ^= 1 << k;
}
}
ans[p] = x;
break;
}
}
}
return ans;
}
}
|
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 | class Solution {
public:
vector<int> findClosedNumbers(int num) {
vector<int> ans(2, -1);
int dirs[3] = {0, 1, 0};
for (int p = 0; p < 2; ++p) {
int a = dirs[p], b = dirs[p + 1];
int x = num;
for (int i = 1; i < 31; ++i) {
if ((x >> i & 1) == a && (x >> (i - 1) & 1) == b) {
x ^= 1 << i;
x ^= 1 << (i - 1);
int j = 0, k = i - 2;
while (j < k) {
while (j < k && (x >> j & 1) == b) {
++j;
}
while (j < k && (x >> k & 1) == a) {
--k;
}
if (j < k) {
x ^= 1 << j;
x ^= 1 << k;
}
}
ans[p] = x;
break;
}
}
}
return ans;
}
};
|
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 | func findClosedNumbers(num int) []int {
ans := []int{-1, -1}
dirs := [3]int{0, 1, 0}
for p := 0; p < 2; p++ {
a, b := dirs[p], dirs[p+1]
x := num
for i := 1; i < 31; i++ {
if x>>i&1 == a && x>>(i-1)&1 == b {
x ^= 1 << i
x ^= 1 << (i - 1)
j, k := 0, i-2
for j < k {
for j < k && x>>j&1 == b {
j++
}
for j < k && x>>k&1 == a {
k--
}
if j < k {
x ^= 1 << j
x ^= 1 << k
}
}
ans[p] = x
break
}
}
}
return ans
}
|
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 | function findClosedNumbers(num: number): number[] {
const ans: number[] = [-1, -1];
const dirs: number[] = [0, 1, 0];
for (let p = 0; p < 2; ++p) {
const [a, b] = [dirs[p], dirs[p + 1]];
let x = num;
for (let i = 1; i < 31; ++i) {
if (((x >> i) & 1) === a && ((x >> (i - 1)) & 1) === b) {
x ^= 1 << i;
x ^= 1 << (i - 1);
let [j, k] = [0, i - 2];
while (j < k) {
while (j < k && ((x >> j) & 1) === b) {
++j;
}
while (j < k && ((x >> k) & 1) === a) {
--k;
}
if (j < k) {
x ^= 1 << j;
x ^= 1 << k;
}
}
ans[p] = x;
break;
}
}
}
return ans;
}
|
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 | class Solution {
func findClosedNumbers(_ num: Int) -> [Int] {
var ans = [-1, -1]
let dirs = [0, 1, 0]
for p in 0..<2 {
let a = dirs[p], b = dirs[p + 1]
var x = num
var found = false
for i in 1..<31 {
if ((x >> i) & 1) == a && ((x >> (i - 1)) & 1) == b {
x ^= (1 << i)
x ^= (1 << (i - 1))
var j = 0, k = i - 2
while j < k {
while j < k && ((x >> j) & 1) == b {
j += 1
}
while j < k && ((x >> k) & 1) == a {
k -= 1
}
if j < k {
x ^= (1 << j)
x ^= (1 << k)
}
}
ans[p] = x
found = true
break
}
}
if !found {
ans[p] = -1
}
}
return ans
}
}
|