解法一
思路和算法
数组 $\textit{nums}$ 的长度是 $n$。对于 $0 \le i < n$ 的每个下标 $i$，满足 $(\textit{ans}[i] ~|~ (\textit{ans}[i] + 1)) = \textit{nums}[i]$。由于 $\textit{nums}[i]$ 是质数，即 $\textit{nums}[i]$ 至少等于 $2$，因此 $\textit{ans}[i]$ 一定是正整数。
最直观的计算 $\textit{ans}[i]$ 的方法是从小到大遍历每个正整数 $x$，寻找满足 $(x ~|~ (x + 1)) = \textit{nums}[i]$ 的最小正整数 $x$ 填入 $\textit{ans}[i]$，如果不存在符合要求的正整数 $x$ 则 $\textit{ans}[i] = -1$。
根据按位或运算的性质，必有 $(\textit{ans}[i] ~|~ (\textit{ans}[i] + 1)) \ge \textit{ans}[i]$，因此当 $\textit{ans}[i] > \textit{nums}[i]$ 时必有 $(\textit{ans}[i] ~|~ (\textit{ans}[i] + 1)) > \textit{nums}[i]$，计算 $\textit{ans}[i]$ 时只需要遍历不超过 $\textit{nums}[i]$ 的值。
代码
###Java
class Solution {
public int[] minBitwiseArray(List<Integer> nums) {
int n = nums.size();
int[] ans = new int[n];
for (int i = 0; i < n; i++) {
ans[i] = find(nums.get(i));
}
return ans;
}
public int find(int num) {
for (int i = 1; i <= num; i++) {
if ((i | (i + 1)) == num) {
return i;
}
}
return -1;
}
}
###C#
public class Solution {
public int[] MinBitwiseArray(IList<int> nums) {
int n = nums.Count;
int[] ans = new int[n];
for (int i = 0; i < n; i++) {
ans[i] = Find(nums[i]);
}
return ans;
}
public int Find(int num) {
for (int i = 1; i <= num; i++) {
if ((i | (i + 1)) == num) {
return i;
}
}
return -1;
}
}
复杂度分析
解法二
思路和算法
当存在正整数 $x$ 满足 $(x ~|~ (x + 1)) = \textit{nums}[i]$ 时，由于 $x$ 和 $x + 1$ 当中一定有一个奇数，因此 $\textit{nums}[i]$ 一定是奇数。如果 $\textit{nums}[i]$ 是偶数，则不存在符合要求的 $x$，对应 $\textit{ans}[i] = -1$。当 $\textit{nums}[i]$ 是奇数时，可以取 $x = \textit{nums}[i] - 1$，则满足 $(x ~|~ (x + 1)) = \textit{nums}[i]$，因此如果 $\textit{nums}[i]$ 是奇数，则一定存在符合要求的 $x$。
由于 $\textit{nums}[i]$ 是质数，唯一的偶质数是 $2$，因此当 $\textit{nums}[i] = 2$ 时 $\textit{ans}[i] = -1$。当 $\textit{nums}[i] > 2$ 时 $\textit{ans}[i] > 0$，需要计算 $\textit{ans}[i]$。
考虑正整数 $x$ 和 $x + 1$ 的二进制表示的如下两种情况。
-
当 $x$ 是偶数时，$x$ 的二进制表示的最低位是 $0$，$x + 1$ 的二进制表示等于 $x$ 的二进制表示的最低位从 $0$ 变成 $1$。
-
当 $x$ 是奇数时，$x$ 的二进制表示最低位有 $k$ 个 $1$ 且从低到高第 $k$ 位等于 $0$（位数从 $0$ 开始计数），其中 $k \ge 1$，$x + 1$ 的二进制表示等于 $x$ 的二进制表示的最低 $k$ 位从 $1$ 变成 $0$ 且从低到高第 $k$ 位从 $0$ 变成 $1$。
因此，$x ~|~ (x + 1)$ 的二进制表示的结果等于 $x$ 的二进制表示的最右边的 $0$ 变成 $1$。
为了使 $\textit{ans}[i]$ 的值最小，需要找到 $\textit{nums}[i]$ 的二进制表示中的可以变成 $0$ 的最左边的 $1$，满足将 $0$ 变成 $1$ 之后在其右侧没有任何 $0$。计算方法如下。
-
计算 $\textit{nums}[i]$ 的二进制表示的最低连续 $1$ 的最大位数 $k$，满足二进制表示最低位有 $k$ 个 $1$ 且从低到高第 $k$ 位等于 $0$（位数从 $0$ 开始计数）。
-
计算 $\textit{ans}[i] = \textit{nums}[i] - 2^{k - 1}$。
根据位运算的性质，计算方法如下：计算 $\textit{lowbit} = ((\textit{nums}[i] + 1) ~&~ (-\textit{nums}[i] - 1)) >> 1$，则 $\textit{lowbit}$ 等于上述 $2^{k - 1}$，$\textit{ans}[i] = \textit{nums}[i] - \textit{lowbit}$。
代码
###Java
class Solution {
public int[] minBitwiseArray(List<Integer> nums) {
int n = nums.size();
int[] ans = new int[n];
for (int i = 0; i < n; i++) {
ans[i] = find(nums.get(i));
}
return ans;
}
public int find(int num) {
if (num % 2 == 0) {
return -1;
} else {
int lowbit = ((num + 1) & (-num - 1)) >> 1;
return num - lowbit;
}
}
}
###C#
public class Solution {
public int[] MinBitwiseArray(IList<int> nums) {
int n = nums.Count;
int[] ans = new int[n];
for (int i = 0; i < n; i++) {
ans[i] = Find(nums[i]);
}
return ans;
}
public int Find(int num) {
if (num % 2 == 0) {
return -1;
} else {
int lowbit = ((num + 1) & (-num - 1)) >> 1;
return num - lowbit;
}
}
}
复杂度分析
登录