给定一个大小为 n 的数组,找到在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。 多数元素是指在数组中出现次数大于⌊ n/2 ⌋的元素。 假设数组是非空的,并且给定的数组总是存在多数元素。0≤n≤5000,数组中的数字都是整数。使用C++
时间: 2024-06-06 15:06:38 浏览: 8
#include <stdio.h>
int main() {
int n, num[5000], i, count = 1, majority = 0;
// 输入
scanf("%d", &n);
for (i = 0; i < n; i++) {
scanf("%d", &num[i]);
}
// 找多数元素
for (i = 1; i < n; i++) {
if (num[i] == num[majority]) {
count++;
} else {
count--;
}
if (count == 0) {
majority = i;
count = 1;
}
}
// 验证多数元素
count = 0;
for (i = 0; i < n; i++) {
if (num[i] == num[majority]) {
count++;
}
}
if (count > n / 2) {
printf("%d\n", num[majority]);
}
return 0;
}
相关问题
给定一个大小为 n 的数组,找到在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
摩尔投票算法可以解决这个问题,算法的基本思想是:每次从数组中选出两个不同的元素,将其删除;如果两个元素相同,则保留一个,并将其删除。这样不断重复,最终剩下的元素就是出现次数大于 ⌊ n/2 ⌋ 的元素。
具体实现如下:
1.假设第一个元素为出现次数大于 ⌊ n/2 ⌋ 的元素,计数器 count 初始化为 1。
2.从第二个元素开始遍历数组,如果当前元素和计数器中的元素相同,则计数器加 1,否则计数器减 1。
3.如果计数器减为 0,则重新将下一个元素设为出现次数大于 ⌊ n/2 ⌋ 的元素,并将计数器设为 1。
4.最终剩下的元素即为出现次数大于 ⌊ n/2 ⌋ 的元素。
代码实现如下(假设数组中一定存在出现次数大于 ⌊ n/2 ⌋ 的元素):
```python
def majorityElement(nums):
candidate = nums[0]
count = 1
for i in range(1, len(nums)):
if nums[i] == candidate:
count += 1
else:
count -= 1
if count == 0:
candidate = nums[i]
count = 1
return candidate
```
时间复杂度为 O(n),空间复杂度为 O(1)。
用C语言实现题目:给定一个大小为 n 的数组,找到在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
一种简单的解决方法是使用哈希表。遍历整个数组,将每个元素作为键,将它们的出现次数作为值存储在哈希表中。最后再遍历一遍哈希表,找到出现次数大于 ⌊ n/2 ⌋ 的元素。
具体实现如下:
```c
#include <stdio.h>
#include <stdlib.h>
#define HASH_SIZE 100
typedef struct node {
int key;
int count;
struct node *next;
} Node;
int hash(int key) {
return key % HASH_SIZE;
}
void insert(Node **hashTable, int key) {
int index = hash(key);
Node *p = hashTable[index];
while (p != NULL) {
if (p->key == key) {
p->count++;
return;
}
p = p->next;
}
Node *newNode = (Node *)malloc(sizeof(Node));
newNode->key = key;
newNode->count = 1;
newNode->next = hashTable[index];
hashTable[index] = newNode;
}
int findMajority(Node **hashTable, int n) {
int threshold = n / 2;
for (int i = 0; i < HASH_SIZE; i++) {
Node *p = hashTable[i];
while (p != NULL) {
if (p->count > threshold) {
return p->key;
}
p = p->next;
}
}
return -1;
}
int main() {
int n;
printf("Enter the size of the array: ");
scanf("%d", &n);
int *a = (int *)malloc(sizeof(int) * n);
printf("Enter the elements of the array: ");
for (int i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
Node **hashTable = (Node **)malloc(sizeof(Node *) * HASH_SIZE);
for (int i = 0; i < HASH_SIZE; i++) {
hashTable[i] = NULL;
}
for (int i = 0; i < n; i++) {
insert(hashTable, a[i]);
}
int majority = findMajority(hashTable, n);
if (majority != -1) {
printf("The majority element is %d\n", majority);
} else {
printf("There is no majority element\n");
}
return 0;
}
```
这里使用了一个简单的哈希函数,将键值取模,将余数作为哈希表的下标。在遍历数组时,将每个元素插入哈希表中。如果已经存在,则增加计数器;否则创建一个新的节点。在查找阶段,遍历哈希表,找到计数器大于阈值的节点即可。如果没找到,则说明没有出现次数大于 ⌊ n/2 ⌋ 的元素。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)