剑指Offer（二十八）：数组中出现次数超过一半的数字

2017年12月20日20:12:13 5 5,447 °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++：

C++
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
class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        if(numbers.empty()){
            return 0;
        }
        // 遍历每个元素，并记录次数；若与前一个元素相同，则次数加1，否则次数减1
        int result = numbers[0];
        int times = 1;
        for(int i = 1; i < numbers.size(); ++i){
            if(times == 0){
                // 更新result的值为当前元素，并置次数为1
                result = numbers[i];
                times = 1;
            }
            else if(numbers[i] == result){
                times++;
            }
            else{
                times--;
            }
        }
        // 判断result是否符合条件，即出现次数大于数组长度的一半
        times = 0;
        for(int i = 0; i < numbers.size(); ++i)
        {
            if(numbers[i] == result){
                times++;
            }
        }
        return (times > (numbers.size() >> 1)) ? result : 0;
    }
};

Python：

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# -*- coding:utf-8 -*-
class Solution:
    def MoreThanHalfNum_Solution(self, numbers):
        # write code here
        result = numbers[0]
        times = 1
        for i in range(1, len(numbers)):
            if times == 0:
                result = numbers[i]
                times = 1
            elif result == numbers[i]:
                times += 1
            else:
                times -= 1
        times = 0
        for i in range(len(numbers)):
            if numbers[i] == result:
                times += 1
        return result if times > len(numbers) // 2 else 0

weinxin
微信公众号
分享技术，乐享生活：微信公众号搜索「JackCui-AI」关注一个在互联网摸爬滚打的潜行者。
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
      回复 2019年3月30日 下午2:01  沙发

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

        • avatar Jack Cui Admin 来自天朝的朋友 谷歌浏览器 Mac OS X 10_14_3 北京市 百度网讯科技联通节点
          回复 2019年4月1日 上午10:37  1层

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

        • avatar jian 谷歌浏览器 Windows 10 北美地区 1
          回复 2020年1月8日 下午11:59  板凳

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

          • avatar Tsai 来自天朝的朋友 Netscape Navigator iPhone iPhone OS 11_2_5 like Mac OS X) AppleWebKit 中国 移动 0
            回复 2020年2月27日 上午12:24  地板

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

              • avatar yjx 来自天朝的朋友 谷歌浏览器 Windows 10 黑龙江省大庆市 电信 0
                回复 2020年3月23日 下午11:54  1层

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