阿里云开发者社区在线编程40.2的幂次方数
微wx笑
2020-07-10【算法】
382
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:
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 | 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:
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 | 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:
性能上没问题,但是有用例不通过
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 | 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、反向思路,求找到了多少个,然后用总数减去找到的就是要删除的;
正确解答:
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 | 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; } } |
简化版本
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 | 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
上一篇:返回列表