带你快速刷完67道剑指offer

如果你想在校招中顺利拿到更好的offer,阿秀建议你多看看前人的经验 ,比如准备简历实习上岸经历校招总结阿里、字节、腾讯、美团等一二线大厂真实面经也欢迎来一起参加秋招打卡活动 等;如果你是计算机小白,学习/转行/校招路上感到迷茫或者需要帮助,可以点此联系阿秀;免费分享阿秀个人学习计算机以来的收集到的好资源,点此白嫖;如果你需要《阿秀的学习笔记》网站中求职相关知识点的PDF版本的话,可以点此下载

# No28、数组中出现次数超过一半的数字

牛客网原题链接 (opens new window)

# 题目描述

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

# 示例1

输入

[1,2,3,2,2,2,5,4,2]
1

返回值

2
1

# 1、常规做法,哈希表

int MoreThanHalfNum_Solution(vector<int> numbers) {
     
    unordered_map<int, int>unmp;
    int len = numbers.size();
    for (int i = 0; i < len; ++i) {
        unmp[numbers[i]]++;
        if (unmp[numbers[i]] > len / 2) return numbers[i];
    }
    return 0;
    }
1
2
3
4
5
6
7
8
9
10

# 二刷:

# 1、摩尔投票法的变种,与力扣上多数元素 (opens new window)是差不多的做法,很高效的一种做法

运行时间:3ms 占用内存:464k

    int MoreThanHalfNum_Solution(vector<int> numbers) {
	//摩尔投票法,成立前提就是有出现超过一半的元素,所以最后我们需要判断找到的元素是否出现超过一半了
	int cnt = 0, num = 0;
	for (int i = 0; i < numbers.size(); ++i) {
		if (cnt == 0) {
			num = numbers[i];
			cnt = 1;
		}
		else {
			num == numbers[i] ? cnt++ : cnt--;
		}

	}
	cnt = count(numbers.begin(), numbers.end(), num);
	return cnt > numbers.size() / 2 ? num : 0;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16