C++实现,给定一个大小为 n 的整数数组,找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。
时间: 2023-02-10 07:16:21 浏览: 130
从N选取M个数的所有组合数C++描述C++描述
4星 · 用户满意度95%
首先,我们可以使用投票算法来找到出现次数大于 ⌊ n/3 ⌋ 次的元素。
基本思想是用两个变量来记录当前数组中出现次数最多的两个元素,遍历数组时,如果当前元素与这两个元素之一相同,则将对应的计数器加 1,否则将两个计数器都减 1。如果两个计数器都减为 0,则清空这两个变量,并用当前元素来替换。
然后我们再遍历一遍数组,计算这两个元素的出现次数,如果大于 ⌊ n/3 ⌋ 次,则将其添加到结果数组中。
以下是 C 语言代码示例:
```
#include <stdio.h>
#include <stdlib.h>
#define min(a, b) ((a) < (b) ? (a) : (b))
int* majorityElement(int* nums, int numsSize, int* returnSize) {
if (numsSize == 0) {
*returnSize = 0;
return NULL;
}
int candidate1 = nums[0], count1 = 0;
int candidate2 = nums[0], count2 = 0;
for (int i = 0; i < numsSize; i++) {
if (nums[i] == candidate1) {
count1++;
} else if (nums[i] == candidate2) {
count2++;
} else if (count1 == 0) {
candidate1 = nums[i];
count1 = 1;
} else if (count2 == 0) {
candidate2 = nums[i];
count2 = 1;
} else {
count1--;
count2--;
}
}
count1 = 0;
count2 = 0;
for (int i = 0; i < numsSize; i++) {
if (nums[i] == candidate1) {
count1++;
} else if (nums[i] == candidate2) {
阅读全文