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
| class Solution {
public int[] findClosedNumbers(int num) {
return new int[]{findBiggerNumber(num), findSmallerNumber(num)};
}
private int findSmallerNumber(int num) {
for (int i = 0; i < 30; i++) {
if (((num >> i) & 1) == 0 && ((num >> (i + 1)) & 1) == 1) {
num = reverseNthBit(num, i);
num = reverseNthBit(num, i + 1);
int j = i - 1, k = 0;
while (k < j) {
while (k < j && ((num >> j) & 1) == 1) {
j--;
}
while (k < j && ((num >> k) & 1) == 0) {
k++;
}
if (k < j) {
num = reverseNthBit(num, j--);
num = reverseNthBit(num, k++);
}
}
return num;
}
}
return -1;
}
private int reverseNthBit(int num, int nth) {
if (((num >> nth) & 1) == 0) {
return num | (1 << nth);
} else {
return num & ~(1 << nth);
}
}
private int findBiggerNumber(int num) {
for (int i = 0; i < 30; i++) {
if (((num >> i) & 1) == 1 && ((num >> (i + 1)) & 1) == 0) {
num = reverseNthBit(num, i);
num = reverseNthBit(num, i + 1);
int j = i - 1, k = 0;
while (k < j) {
while (k < j && ((num >> j) & 1) == 0) {
j--;
}
while (k < j && ((num >> k) & 1) == 1) {
k++;
}
if (k < j) {
num = reverseNthBit(num, j--);
num = reverseNthBit(num, k++);
}
}
return num;
}
}
return -1;
}
}
|
对于二进制表示来说，容易想到的是，如果需要寻找更大的数且二进制表达式中 1 的个数相同，那么就需要寻找二进制 01，将其调整为这两个比特位调整为 10 即找到更大的数，同理如果需要寻找更小的数且二进制表达式中 1 的个数相同，那么就需要寻找二进制 10，将其调整为 01 即找到更小的数。但是以上找到的数并不是最接近的更大的数/更小的数。比如二进制 1001，其更小的数二进制表达式应该为 0110 而不应该是 0101，即在将最右侧的 10 调整为 01 后，还要将右侧剩余的 1 挪动至左侧，才能保证找到的数为最接近的数。可参考：31. Next Permutation。
References
面试题 05.04. 下一个数