第一次见到这个题,感觉简单到爆,不就是sort函数排个序,取中位数,遍历一遍计个数不就OK了吗?但是面试时,sort可能会让你自己去实现,或者说,题目要求:不能修改输入的数组呢???
第一种方法(基于Partition函数)
注意:此方法修改了输入的数组
创新互联建站坚持“要么做到,要么别承诺”的工作理念,服务领域包括:成都做网站、网站制作、成都外贸网站建设、企业官网、英文网站、手机端网站、网站推广等服务,满足客户于互联网时代的泗水网站设计、移动媒体设计的需求,帮助企业找到有效的互联网解决方案。努力成为您成熟可靠的网络建设合作伙伴!
核心:出现次数超过一半的数字,排序后中位数肯定是这个数字
解题思路:通过Partition函数,随机选出数组中的一个元素(我的代码中默认是数组中第一个元素),并且通过快排的思想,小的元素移到随机值前面,大的元素移到随机值的后面,然后返回随机值最后的位置。然后通过调用Partition函数,用返回的index值和中值判等,如果index>mid,说明中位数在左边,end=mid-1,如果index 第二种方法(计数法) 核心:出现次数超过一半的数字个数比其他所有数字个数至少多一 解题思路:从首位开始(result==numbers[0]),遇到相等的元素,count++,遇到不相等的元素,count--,当count==0时,result重新赋值为当前元素,重新给count赋值为1,直到数组遍历完之后,返回result 疑惑???既然,判断出来了,为什么还要调用Check函数,因为我们无法判断result是否为出现次数最多的元素,就算是出现次数最多的元素,不知是否超过数组一半,例如:{5,5,5,5,5,3,3,3,4,4,4,4} {3,3,3,4,4,4,4,5,5,5,5,5}class Solution {
public:
int MoreThanHalfNum_Solution(vector
注意:此方法没有修改输入的数组class Solution {
public:
int MoreThanHalfNum_Solution(vector
本文名称:数组中出现次数超过一半的数字(C++剑指Offer详解)
当前链接:http://cdkjz.cn/article/pgjijh.html