阿里云开发者社区在线编程40.2的幂次方数
微wx笑
2020-07-10【算法】
11
0关键字：
阿里云 开发者社区 在线编程 幂次方数
2的幂次方数概述：Tom是一个十分喜欢数学的人，尤其喜欢2的幂次方的数字。现有n（1<=n<=150000）个数字，对于其中的每一个数字ai(1<=i<n, 1<=ai<=1000000000)，Tom希望找到除了它自己以
2的幂次方数
概述：
Tom是一个十分喜欢数学的人，尤其喜欢2的幂次方的数字。现有n（1<=n<=150000）个数字，对于其中的每一个数字ai(1<=i<n, 1<=ai<=1000000000)，Tom希望找到除了它自己以外的一个数aj(i!=j)，使得ai+aj是一个2的幂次方数，如果找不到就将这个数删除，问最终需要删除多少个数字。
输入数字个数n和n个数字
输出一个数字，表示最终需要删除的数字的个数。
官方给出的思路：
参考：https://developer.aliyun.com/article/746602?spm=a2c6h.12873639.0.0.14714b6e8UF4Ru
解题方法 ：位运算
对于本题，因为要从数组中删除数字。删除分为两步，一是定位（查找），二是删除（将出现次数减1）。所以首先需要考虑的难题是，如何快速定位要查找的数字，并记录下数字出现的次数？for循环的线性查找，递归的二分查找（对有序数组），建立哈希表，都是可选的方式。既然追求最佳解法，你不妨先试试将题目提供的数据结构转为哈希表？
之后的第二个难点，就是如何得出“与某个数相加为2的幂次方数”的数字了。我们知道，用二进制表示时，一个2的幂次方的正整数，譬如2，4，8，16...，只有最高位为1，其余位都是0，譬如b1，b10，b100，b1000...所以，对每个数字，只要用位元算找到它的最高位1的位置，就可以确定比它大的2的幂次方数中最小的数字了。
本题最后的陷阱，在于正确理解 “与这个数相加为2的幂次方数”的条件。举个例子来说，对于数字1，它不仅与1相加为2的幂次方数，与3，7，15...相加后，结果都是2的幂次方数。很多同学想到位运算的时候，可能忽略了这个条件，而只考虑了比数字大的2的幂次方数中最小的数字
时间复杂度：O(31n)（考虑到本题Integer正整数所占的二进制位数
空间复杂度：O(n)
这道题对算法的效率要求很高，尝试了几种方法都是本地通过，提交之后不通过：
算法1：
package solution40;
import java.awt.List;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.Arrays;
import java.util.HashMap;
class Solution {
public static boolean ispow(int i){
if(i<=1){
return false;
}
do{
if((i&1)!=0){
return false;
}
i=i/2;
}while(i!=1);
return true;
}
public int solution(int n,int[] nums) {
int c = 0;
for (int i=0;i<n-1;i++){
for(int j=1; j<n;j++){
if (i == j){
break;
}
if (!ispow(nums[i]+nums[j])){
c++;
}
}
}
return c;
}
}算法2：
package solution40;
class Solution {
public int solution(int n,int[] nums) {
int dels = 0;
int sum;
boolean isFind;
for (int i = 0; i < n-1; i++) {
isFind=false;
for (int j = 1; j < n - i - 1; j++) {
if (i != j ) {
sum = nums[i] + nums[i+j];
if (((sum & (sum - 1)) == 0)) {
isFind=true;
break;
}
}
}
if(!isFind) {
dels++;
}
}
return dels;
}
}算法3：
性能上没问题，但是有用例不通过
package solution40;
class Solution {
public int solution(int n,int[] nums) {
int dels = 0;
int sum;
for (int i = 0; i < n; i++) {
for (int j = 1; j < n - i - 1; j++) {
if (i != j ) {
sum = nums[i] + nums[i+j];
if (((sum & (sum - 1)) == 0)) {
i+=j;
dels+=j;
break;
}
}else{
dels++;
i++;
}
}
}
return dels;
}
}白话解题思路
1、对传入的数组去重；
2、利用Map的优势做反向查找，而不是遍历数组；
3、反向思路，求找到了多少个，然后用总数减去找到的就是要删除的；
正确解答：
package solution40;
import java.util.*;
class Solution {
public static int solution(int n,int[] nums) {
int count = 0;
boolean tags[] = new boolean[n];
Map<Integer, List<Integer>> map = new HashMap<Integer, List<Integer>>();
for (int i = 0; i < n; i++) {
if (map.get(nums[i]) != null) {
map.get(nums[i]).add(i);
} else {
map.put(nums[i], new ArrayList<>(Arrays.asList(i)));
}
}
int[] m30 = new int[30];
for (int i = 0; i < 30; i++) {
m30[i] = (1 << i);
}
for (Map.Entry<Integer, List<Integer>> entry : map.entrySet()) {
for (int i = 0; i < 30; i++) {
int ai = entry.getKey();
int aj = m30[i] - ai;
if (map.get(aj) != null) {
if (!(map.get(aj).size() == 1 && map.get(aj).get(0) == map.get(ai).get(0))) {
map.get(aj).forEach(o -> tags[o] = true);
map.get(ai).forEach(o -> tags[o] = true);
}
}
}
}
for (boolean t : tags)
if (t)
count++;
return n - count;
}
}简化版本
package solution40;
import java.util.*;
class Solution {
public static int solution(int n,int[] nums) {
Map<Integer, Boolean> tags = new HashMap<Integer, Boolean>();
Map<Integer, List<Integer>> map = new HashMap<Integer, List<Integer>>();
for (int i = 0; i < n; i++) {
if (map.get(nums[i]) != null) {
map.get(nums[i]).add(i);
} else {
map.put(nums[i], new ArrayList<Integer>());
map.get(nums[i]).add(i);
}
}
for (Map.Entry<Integer, List<Integer>> entry : map.entrySet()) {
for (int i = 0; i < 30; i++) {
int ai = entry.getKey();
int aj = (1 << i) - ai;
if (map.get(aj) != null) {
if (!(map.get(aj).size() == 1 && map.get(aj).get(0) == map.get(ai).get(0))) {
map.get(aj).forEach(o -> tags.put(o, true));
map.get(ai).forEach(o -> tags.put(o, true));
}
}
}
}
return n - tags.size();
}
}本文由 微wx笑 创作，采用 署名-非商业性使用-相同方式共享 4.0 许可协议，转载请附上原文出处链接及本声明。
原文链接：https://www.ivu4e.cn/blog/algorithm/2020-07-10/503.html
上一篇：返回列表
