c语⾔怎么去出数组中的众数，算法（LeetCode）六种⽅法求
数组中的绝对众数
原题来⾃:LEETCODE。
定义：绝对众数就是⼀个数在⼀组数中个数超过1/2的数。
⽐如给你⼀个长度为N的整形数组：
[13,12,53,12,23,343,12,12]
要求出他们之中出现次数超过N/2的元素(假定⼀个数组中必定会有这样的元素)，你会怎么求？若你是暴⼒求解，时间复杂度为O(n^2)，那就low啦！
下⾯是LeetCode上某位题友给出的六种算法，括号中是我测试出来的每个算法通过OJ的平均时间，我们来⼀个⼀个地讲解。
哈希表 (22ms)
排序法 (23ms)
随机数法 (19ms)
摩尔投票法 (19ms)
分治法 (26ms)
位操作法 (25ms)
下⾯⼀个⼀个地讲解。
⼀、哈希表法
代码：
int majorityElement(std::vector &nums){
std::map counter;
for (int i = 0; i < nums.size(); ++i)
if(++counter[nums[i]] > nums.size()/2)
return nums[i];
}
利⽤哈希表，将每个数值的次数存放起来，遇到⼀个就对应加⼀，直到这个数值的次数⼤于n/2为⽌(注意只可能有⼀个数，出现的次数⼤于n/2).
⼆、排序法
代码：
int majorityElement(std::vector &nums){
nth_element(nums.begin(),nums.begin()+nums.size()/d());
return nums[nums.size()/2];
}
代码最简洁，仅仅两句。也很容易理解，运⽤了STL中的nth_element(). 通过调⽤nth_element(start, start+n, end)⽅法，可以使第n个⼤的数值的位置之前的元素都⼩于这个位置的元素，这个位置之后的
元素都⼤于这个位置的元素。但是他们不⼀定是有序的。由于我们的绝对众数出现的次数⼤于n/2，所以排序后第n/2⼤的元素⼀定是这个绝对众数。
三、随机数法
代码：
int majorityElement(std::vector &nums){
srand((unsigned)time(NULL));
//得到随机数种⼦
while (1) {
int counters = 0;
int index = rand() % nums.size();
for (int i = 0; i < nums.size(); ++i) {
if (nums[index] == nums[i]){
++counters;
}
if (counters > nums.size()/2){
return nums[index];
}
}
}
}
原理：随机到⼀个数然后计算这个数组⾥这个数出现的次数，若⼤于n/2则返回这个数。
我⼀开始以为这个算法会⾮常慢，因为它最坏情况是O(n^2)，但出乎意料，44个测试的平均结果中，它⼏乎是最快的算法(19ms)，和摩尔投票法相当。
四、摩尔投票法(动态规划)
代码：
int majorityElement(std::vector &nums){
int major = 0, counters = 0;
for (int i = 0; i < nums.size(); ++i) {
if(!counters){
major = nums[i];
counters = 1;
}
else
counters += (major == nums[i]) ? 1:-1;
}
return major;//因为假设⼀定存在绝对众数，所以可以直接返回
原理：定位major为数组中的某个数，遇到同样的数加⼀，不同的数减⼀，若为0则去掉这个定位，重新定位另外⼀个数，最后要么返回绝对众数，要么不存在绝对众数，由于题⽬中已经假设⼀定存在绝对众数，所以不存在的情况不需要考虑。
五、分治法
代码：
int majorityElement(std::vector &nums){
return majority(nums, 0, nums.size()-1);
}
int majority(std::vector &nums,int left,int right){
if (left == right) {
return nums[left];
}
int mid = left + ((right - left) >> 1);
int lm = majority(nums, left, mid);
int rm = majority(nums, mid + 1, right);
if(lm == rm){
return rm;
}
return std::count(nums.begin() + left, nums.begin() + right + 1, lm) > std::count(nums.begin() + left, nums.begin() + right + 1, rm) ? lm : rm;
}
原理：通过分治的思想计算出左右两边出现次数最多的数，然后进⾏⽐较，看哪个出现的次数更多，返回次数更多的那⼀个。值得注意的是这⾥⽤到了STL⾥的count⽅法，它使⽤⼀对迭代器和⼀个值做
参数，将值出现的次数返回。
PS：中间计算mid的时候⽤到了位操作符，>>1其实就是除以2. 不能直接(left+right)/2，因为left+right可能会溢出。
六、位操作法
代码：
int majorityElement(vector & nums) {int major = 0;
for (int i = 0,mask = 1; i < 32; ++i,mask <<= 1) {
int bitCounts = 0;
for (int j = 0; j < nums.size(); ++j) {
if(nums[j] & mask) bitCounts++;
if (bitCounts > nums.size()/2) {
major |= mask;
break;
}
c语言如何去学
}
return major;
}
原理：这是最有趣的⼀个算法，它算的是每个数的bit(位)，若所有数字的某个bit(位)的个数加起来⼤于⼀半，则绝对众数⼀定有这个位，把这个位的值加起来，最后得到的结果就是绝对众数。
PS:(major |= mask 中的 |= 是按位或，其实就相当于+=),(& 就是“与”运算符，返回两个数值中位置⼀样的位的值)
若还是⽆法理解，希望下⾯这张图能够帮助你理解这个算法。字丑见谅~
欢迎关注：幻象客
欢迎进⼊极致分享：
赞赏
⼈赞赏

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。