算法您现在的位置是:首页 > 博客日志 > 算法

阿里云开发者社区在线编程40.2的幂次方数

<a href='mailto:'>微wx笑</a>的头像微wx笑2020-07-10 21:43:18算法人已围观关键字: 阿里云  开发者社区  在线编程  幂次方数  

2的幂次方数概述:Tom是一个十分喜欢数学的人,尤其喜欢2的幂次方的数字。现有n(1<=n<=150000)个数字,对于其中的每一个数字ai(1<=i<n, 1<=ai<=1000000000),Tom希望找到除了它自己以

2的幂次方数lca编程技术_踩坑日志_进阶指南_无知人生

概述:lca编程技术_踩坑日志_进阶指南_无知人生

Tom是一个十分喜欢数学的人,尤其喜欢2的幂次方的数字。现有n(1<=n<=150000)个数字,对于其中的每一个数字ai(1<=i<n, 1<=ai<=1000000000),Tom希望找到除了它自己以外的一个数aj(i!=j),使得ai+aj是一个2的幂次方数,如果找不到就将这个数删除,问最终需要删除多少个数字。
输入数字个数n和n个数字
输出一个数字,表示最终需要删除的数字的个数。lca编程技术_踩坑日志_进阶指南_无知人生

官方给出的思路:

参考:https://developer.aliyun.com/article/746602?spm=a2c6h.12873639.0.0.14714b6e8UF4Rulca编程技术_踩坑日志_进阶指南_无知人生

解题方法 :位运算

对于本题,因为要从数组中删除数字。删除分为两步,一是定位(查找),二是删除(将出现次数减1)。所以首先需要考虑的难题是,如何快速定位要查找的数字,并记录下数字出现的次数?for循环的线性查找,递归的二分查找(对有序数组),建立哈希表,都是可选的方式。既然追求最佳解法,你不妨先试试将题目提供的数据结构转为哈希表?lca编程技术_踩坑日志_进阶指南_无知人生

之后的第二个难点,就是如何得出“与某个数相加为2的幂次方数”的数字了。我们知道,用二进制表示时,一个2的幂次方的正整数,譬如2,4,8,16...,只有最高位为1,其余位都是0,譬如b1,b10,b100,b1000...所以,对每个数字,只要用位元算找到它的最高位1的位置,就可以确定比它大的2的幂次方数中最小的数字了。lca编程技术_踩坑日志_进阶指南_无知人生

本题最后的陷阱,在于正确理解 “与这个数相加为2的幂次方数”的条件。举个例子来说,对于数字1,它不仅与1相加为2的幂次方数,与3,7,15...相加后,结果都是2的幂次方数。很多同学想到位运算的时候,可能忽略了这个条件,而只考虑了比数字大的2的幂次方数中最小的数字lca编程技术_踩坑日志_进阶指南_无知人生

时间复杂度:O(31n)(考虑到本题Integer正整数所占的二进制位数lca编程技术_踩坑日志_进阶指南_无知人生

空间复杂度:O(n)lca编程技术_踩坑日志_进阶指南_无知人生


lca编程技术_踩坑日志_进阶指南_无知人生


lca编程技术_踩坑日志_进阶指南_无知人生

这道题对算法的效率要求很高,尝试了几种方法都是本地通过,提交之后不通过:lca编程技术_踩坑日志_进阶指南_无知人生

算法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:

性能上没问题,但是有用例不通过lca编程技术_踩坑日志_进阶指南_无知人生

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、对传入的数组去重;lca编程技术_踩坑日志_进阶指南_无知人生

2、利用Map的优势做反向查找,而不是遍历数组;lca编程技术_踩坑日志_进阶指南_无知人生

3、反向思路,求找到了多少个,然后用总数减去找到的就是要删除的;lca编程技术_踩坑日志_进阶指南_无知人生

正确解答:

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();
    }
}


lca编程技术_踩坑日志_进阶指南_无知人生

本文由 微wx笑 创作,采用 CC BY-NC 4.0 许可协议。 非商业性使用可自由转载、引用、甚至修改,但需署名作者且注明出处。

很赞哦! () 有话说 ()