剑指Offer(二十八):数组中出现次数超过一半的数字

2017年12月20日20:12:13 5 3,567 °C
摘要

数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2。如果不存在则输出0。

剑指Offer(二十八):数组中出现次数超过一半的数字

一、前言

本系列文章为《剑指Offer》刷题笔记。

刷题平台:牛客网

书籍下载:共享资源

二、题目

数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2。如果不存在则输出0。

1、思路

数组中有一个数字出现的次数超过数组长度的一半,也就是说它出现的次数比其他所有数字出现次数的和还要多。因此我们可以考虑在遍历数组的时候保存两个值:一个是数组的一个数字,一个是次数。当我们遍历到下一个数字的时候,如果下一个数字和我们之前保存的数字相同,则次数加1;如果下一个数字和我们之前保存的数字不同,则次数减1。如果次数为零,我们需要保存下一个数字,并把次数设为1。由于我们要找的数字出现的次数比其他所有数字出现的次数之和还要多,那么要找的数字肯定是最后一次把次数设为1时对应的数字。

2、代码

C++:

Python:

weinxin
微信公众号
分享技术,乐享生活:Jack Cui公众号每周五推送“程序员欢乐送”系列资讯类文章,欢迎您的关注!
Jack Cui

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

目前评论:5   其中:访客  4   博主  1

    • avatar ruiqi08 来自天朝的朋友 谷歌浏览器 Mac OS X 10_13_4 北京市 百度网讯科技联通节点 0

      其实只需要遍历1次就可以判断了。遍历1遍后,times值大于1,则对应result符合题目,否则不存在超过1半的数字

        • avatar Jack Cui Admin 来自天朝的朋友 谷歌浏览器 Mac OS X 10_14_3 北京市 百度网讯科技联通节点

          @ruiqi08 大于1也不一定符合吧,也可能没有超过一半。需要再验证一下,例如:1,3,2,2,2,5,4,2

        • avatar jian 谷歌浏览器 Windows 10 北美地区 1

          这个逻辑有些不太对,如22234577,虽然结果是对的,输出0,但是逻辑上应该拿2的个数与数组一半去比,而不是7个数。当然,2没有被选中就说明个数小于一半了。

          • avatar Tsai 来自天朝的朋友 Netscape Navigator iPhone iPhone OS 11_2_5 like Mac OS X) AppleWebKit 中国 移动 0

            2 2 3 3 1 4 2 这个就不对啊 到2的时候刚好为1 但是次数并没有超过一半

              • avatar yjx 来自天朝的朋友 谷歌浏览器 Windows 10 黑龙江省大庆市 电信 0

                @Tsai 如果没有大于一半的数字,最后一个肯定times会被设为一吧,所以要像楼主一样在遍历一次验证。