【力扣】[剑指 Offer 39.] 数组中出现次数超过一半的数字

1.题目

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

链接：https://leetcode-cn.com/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof/

2.代码展示

int majorityElement(int* nums, int numsSize){ // 根据题意说找到大于数组长度一般的数字并返回 // 这里采用摩尔投票法 // count计数，num记录数组数字 int count = 0; int num = 0; for(int i = 0; i < numsSize; i++) { // 对于count等于0，则用num记录这个数 if(count == 0) { num = nums[i]; } // 对于数字相同的则count++，反之-- if(num == nums[i]) count++; else count--; } return num; }

 

3.牛客网

链接：https://www.nowcoder.com/questionTerminal/e8a1b01a2df14cb2b228b30ee6a92163

class Solution { public: int MoreThanHalfNum_Solution(vector<int> numbers) { // 判空和numbers的元素如果是一个，则直接返回第一个元素 if(numbers.empty()) return 0; if(numbers.size() == 1) return numbers[0]; // 如果count==0，那么numbers[0]会多循环一次，所以count==1 int count = 1; int num = numbers[0]; int len = numbers.size(); for(int i = 1; i < len; i++) { // 如果相等，那么count++，反之则-- if(num == numbers[i]) count++; else count--; if(count == 0) { // 记录每次的数字 num = numbers[i]; count = 1; } } count = 0; // 重新算count的个数，如果大于直接返回记录的num，反之返回0 for(int i = 0; i < len; i++) { if(num == numbers[i]) count++; } return count > (len / 2) ? num : 0; } };

4.摩尔投票法

每次从数组中找出一对不同的元素，将它们从数组中删除，直到遍历完整个数组。由于这道题已经说明一定存在一个出现次数超过一半的元素，所以遍历完数组后数组中一定会存在至少一个元素。  算法在局部变量的定义一个数组元素num和一个计数器count=0算法一次扫描数组中的元素，当处理到x的时候，如果计数器count为0，那么就将x赋值给num，将计数器count+1如果计数器count不为0，则如果x和num相等，那么count++，反之count–处理之后，那么num中存储的就是数组中最多的元素