笔试算法模拟题精解之“2的幂次方数”-阿里云开发者社区

开发者社区> 算法编程> 正文

笔试算法模拟题精解之“2的幂次方数”

简介: 对于本题,因为要从数组中删除数字。删除分为两步,一是定位(查找),二是删除(将出现次数减1)。

【在线编程产品介绍】

阿里云开发者社区在线编程:

免费刷题大神器,助你拿到好offer

周赛月赛不停歇,做题还能领奖品

大赛笔试全真题,常做常新有惊喜

点击链接开始产品体验:https://developer.aliyun.com/coding

本文为大家介绍的是“40.2的幂次方数”的解法探究。先来看一下题目内容:

题目详情

查看题目:2的幂次方数Tom是一个十分喜欢数学的人,尤其喜欢2的幂次方的数字。现有n(1<=n<=150000)个数字,对于其中的每一个数字ai(1<=i输入数字个数n和n个数字;
输出一个数字,表示最终需要删除的数字的个数。
示例1
输入:
3
[1,2,3]
输出:
1

解题方法 :位运算

对于本题,因为要从数组中删除数字。删除分为两步,一是定位(查找),二是删除(将出现次数减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)

看完之后是不是有了答题思路了呢,快来练练手吧:第40题.2的幂次方数

在线编程周赛、月赛火热进行中,更有限时答题活动,社区定制卫衣、双肩背包等你来拿~每天都有好礼相送~点击了解周赛详情:在线编程内测中,抢先周赛赢好礼!面试考试前,快来刷刷题!

b462f1d86b44481ca24c0ad63fe55948.png

上一篇:笔试算法模拟题精解之“Alice的01串”的三种解法

版权声明:本文中所有内容均属于阿里云开发者社区所有,任何媒体、网站或个人未经阿里云开发者社区协议授权不得转载、链接、转贴或以其他方式复制发布/发表。申请授权请邮件developerteam@list.alibaba-inc.com,已获得阿里云开发者社区协议授权的媒体、网站,在转载使用时必须注明"稿件来源:阿里云开发者社区,原文作者姓名",违者本社区将依法追究责任。 如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件至:developer2020@service.aliyun.com 进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
+ 订阅

开发者社区在线编程频道官方技术圈。包含算法资源更新,周赛动态,每日一题互动。

官方博客
官网链接