题目如图所示
算法思想（C语言）:
题目告之序列A中所有的元素小于其序列长度n，大于等于0，故有了以空间换时间的想法。动态申请一个数组，在第一个循环中初始化为0，在第二个循环中以A中元素作为下标，记录A中各个不同元素的出现次数，在第三个循环中也以A中元素作为下标，直到或者找到一个出现次数大于n/2的元素，记录在k中，或者没有找到，由于k已经初始化为-1，无论那种情况直接输出k的值就可以。
个人代码如下
#include#includevoid Func(int A[], int n){//动态申请一个数组，用于记录A中各个不同元素的出现次数int* arr = (int*)malloc(n * sizeof(int));//初始化为0for (int i = 0; i < n; i++)arr[i] = 0;//以A中元素作为下标，记录A中各个不同元素的出现次数for (int i = 0; i < n; i++)arr[A[i]]++;//用k记录是否找到一个元素出现次数大于n / 2int k = -1;for (int i = 0; i < n; i++){if (arr[A[i]] > n / 2){k = A[i];break;}}//输出k，并释放申请的动态数组printf("%d", k);free(arr);}int main(){int n;printf("请输入数组长度\n");scanf("%d", &n);int* A = (int*)malloc(n * sizeof(int));printf("请输入数据\n");for (int i = 0; i < n; i++)scanf("%d", &A[i]);Func(A, n);return 0;}
时间复杂度O(3n)，空间复杂度O(n)