首页 > 代码库 > 题目:大整数乘法、除法,楼梯走法,数组中不同数字,超过一半数字(好)
题目:大整数乘法、除法,楼梯走法,数组中不同数字,超过一半数字(好)
大整数乘法,可以用单个数字想乘,跟踪进位信息来处理。
大整数除法,可以先把除数增大到跟被除数相同的量级,然后累计相减。比如 555 / 3,就先把3增大到300,555能够减1次,那么结果+100,被除数变成255,依次进行。
楼梯走法:一次走一级,或者走两级。没什么难度。
数组中不同数字:如果是2n+1数组找出不同的那个数字,用异或就可以。
如果是找出超出一般数目的数字,用遍历,看到不一样的,就一起删除,这样的方式。
上网搜了一下,找出了更好的方法:
用变量记录备选数字,一个计数器记录该数字剩余的次数。备选数字初始化为第一个元素,计数器为1。
当遇到相同的数字,则计数器+1;当遇到不同的数字,计数器-1;如果计数器<0,则备选数字设为当前数,并且计数器重置为1.
最后,备选数字就是出现次数 > 一半的数字(注意是严格大于,等于是不满足这个算法的)。等于的话,有可能最后一对保存的是次数很少的数,而不是到达一半的数字。
关键这类题目还有很多引申。
题目:大整数乘法、除法,楼梯走法,数组中不同数字,超过一半数字(好)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。