Leetcode - 剑指offer 面试题29：数组中出现次数超过一半的数字及其变形(腾讯2015秋招 编程题4)
剑指offer 面试题29：数组中出现次数超过一半的数字
参与人数：3512 时间限制：1秒 空间限制：32768K
本题知识点： 数组
题目描述
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
分析：
当测试用例出现不到一半的情况，应该输出0。
方法1：快排，如果出现次数超过一半数目的数存在，则该值一定与中位数相等，将其返回；否则返回0. 快排复杂度为n*log n.
另外此题据说有O(n)复杂度的算法...
AC代码：
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
class Gift {
public:
int getValue(vector<int> gifts, int n) {
if(gifts.size()==0 || n<=0) return 0;
// if(gifts.size()!=n) return 0; // 此语句有无，在牛客网oj上均能通过，按道理应加上的...
sort(gifts.begin(),gifts.end());
int countMid=0, res;
for(int i=0; i<gifts.size();i++)
{
if(gifts[i] >= gifts[n/2]) countMid++;
}
if(countMid>n/2) res=gifts[n/2];
else res=0;
return res;
}
};
// 以下为测试
int main()
{
Gift sol;
int n1=5;
vector<int> gifts1={1,2,3,2,2};
int res1=sol.getValue(gifts1, n1);
printf("%d\n",res1);
return 0;
} 腾讯 2015秋招 编程题4：微信红包中个数超过总数一半的红包金额
题目描述
春节期间小明使用微信收到很多个红包，非常开心。在查看领取红包记录时发现，某个红包金额出现的次数超过了红包总数的一半。请帮小明找到该红包金额。写出具体算法思路和代码实现，要求算法尽可能高效。
给定一个红包的金额数组 gifts及它的大小 n，请返回所求红包的金额。
测试样例：
[1,2,3,2,2],5
返回：2
AC代码：
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
class Gift {
public:
int getValue(vector<int> gifts, int n) {
if(gifts.size()==0 || n<=0) return 0;
// if(gifts.size()!=n) return 0; // 此语句有无，在牛客网oj上均能通过，按道理应加上的...
sort(gifts.begin(),gifts.end());
int countMid=0, res;
for(int i=0; i<gifts.size();i++)
{
if(gifts[i] >= gifts[n/2]) countMid++;
}
if(countMid>n/2) res=gifts[n/2];
else res=0;
return res;
}
};
// 以下为测试
int main()
{
Gift sol;
int n1=5;
vector<int> gifts1={1,2,3,2,2};
int res1=sol.getValue(gifts1, n1);
printf("%d\n",res1);
return 0;
} 这道题最优的解法类似于 《编程之美》中"寻找水王"的问题，时间复杂度为O(n)，空间复杂度O(1)。
169. Majority Element( 求众数)
提交网址： https://leetcode.com/problems/majority-element/
Total Accepted: 113359 Total Submissions: 273577 Difficulty: EasyGiven an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.
You may assume that the array is non-empty and the majority element always exist in the array.
Credits:
Special thanks to @ts for adding this problem and creating all test cases.
AC代码：
class Solution {
public:
int majorityElement(vector<int>& numbers) {
int len=numbers.size();
if(len==0) return 0;
sort(numbers.begin(),numbers.end());
int countMid=0, res;
for(int i=0; i<numbers.size();i++)
{
if(numbers[i] == numbers[len/2]) countMid++;
}
if(countMid>len/2) res=numbers[len/2];
else res=0;
return res;
}
};
长安汽车成长空间 27人发布