数据结构代码题？

Question

已知一个整数序列A=(a0，a1，…，an-1)，其中0≤ai＜n(0≤i＜n)。若存在ap1=ap2=…=apm=x且m＞n/2(0≤pk＜n，1≤k≤m)，则称x为A的主元素。例如A=(0，5，5，3，5，7，5，5)，则5为主元素；又如A=(0，5，5，3，5，1，5，7)，则A中没有主元素。假设A中的n个元素保存在一个一维数组中，请设计一个尽可能高效的算法，找出A的主元素。若存在主元素，则输出该元素；否则输出-1。要求：给出算法的基本设计思想。
请用C语言实现
1：按照空间换时间的思想，构建大小为N的数组，用于对每个整数计数，遍历一遍序列后再遍历1次这个数组找最大值
2：对整个序列排序再遍历序列看哪个元素最多
用这两种思想的其中一种完成代码 谢谢！

Answer 1

fisrt

second

#include <iostream>

#include <algorithm>

#define MAX_SIZE 10000

using namespace std;

void first_way(int *arr, int n)

{

int map[MAX_SIZE] = { 0 };//这里元素最大不超过9999，可以按需求放大一些

for (size_t i = 0; i < n; i++)

{

map[arr[i]]++;

}

int main_elem = 0;

for (size_t i = 0; i < MAX_SIZE; i++)

{

if (map[main_elem] < map[i]) main_elem = i;

}

if (map[main_elem] > n / 2) cout << main_elem << endl;

else cout << -1 << endl;

}

void sec_way(int *arr, int n)

{

sort(arr, arr + n);

int count = 1, max_count = 1;

int main_elem = arr[0];

for (size_t i = 1; i < n; i++)

{

if (arr[i] != arr[i - 1])

{

if (count > max_count)

{

max_count = count;

main_elem = arr[i - 1];

}

count = 0;

}

count++;

}

if (count > n / 2) cout << arr[n - 1] << endl;

if (max_count > n / 2) cout << main_elem << endl;

else cout << -1 << endl;

}

int main()

{

int arr1[8] = { 0, 5, 5, 3, 5, 7, 5, 5 };

int arr2[8] = { 0, 5, 5, 3, 5, 1, 5, 7 };

cout << "第一个数组测试：" << endl;

first_way(arr1, 8);

sec_way(arr1, 8);

cout << "第二个数组测试：" << endl;

first_way(arr2, 8);

sec_way(arr2, 8);

    return 0;

}

Answer 2

您好，已经解决了

---

#include <stdio.h>

#include <stdlib.h>

int main()

{

int i, k;

int n = 10;

int x, a[100] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

printf("x=\n");

scanf("%d", &x);

for(i = n - 1; i >= 0 && a[i] > x; i--)

  a[i + 1] = a[i];

a[i + 1] = x;

n++;

for(i = 0; i < n; i++) // 依次输出线性表中的元素

  printf("%d ", a[i]);

return 0;

}

---

采纳 哦~

本回答被网友采纳