一、前言
前几天在leetcode刷题时遇到了这个需求，就来CSDN搜索解决方法。
逛了一大圈，发现最多的方法是：新建一个大小为原数组中最大值的数组（初始化为0），然后遍历原数组，例如遍历到元素a，那么新建数组nums[a]++。最终再遍历一次新建数组，就可以知道哪个元素出现次数最多，以及其出现次数。
先说说这种方法的弊端：
首先如果数组中的最大元素值很大，那么就要创建一个很大的数组，不说浪费空间的问题，问题是有没有这么大的一片连续空间，让我们去申请。
其次是这么长的数组，遍历的时间复杂度也相当高。
所以我个人认为这个方法其实并不可行。
二、我的方法
我自己想的一个方法，大家可以看看：
新建一个和原数组相同的数组Nums，并降序排序。设置度degree（即元素出现次数），默认大小为1（因为每个元素至少出现一次）。遍历数组Nums，如果某元素和其下一元素相等，则degree++，如果不相等，则degree重置为1。每遍历一个元素，都要取最大的degree。这样就能得到数组中出现最多次数元素的出现次数max。
int cmp(const void* e1, const void* e2) { return *(int*)e1 - *(int*)e2; } //函数参数是要查找最多出现元素的数组以及该数组的大小 //int findShortestSubArray(int* nums, int numsSize) int* Nums = (int*)malloc(sizeof(int) * numsSize); //拷贝原数组数据到新数组 for (int i = 0; i < numsSize; i++) { Nums[i] = nums[i]; } qsort(Nums, numsSize, sizeof(int), cmp);//升序排序新数组 int degree = 1;//元素出现次数（度） int max = degree;//初始时，最大次数默认为1 for (int i = 0; i < numsSize - 1; i++) { if (Nums[i] == Nums[i + 1]) { degree++; } else { degree = 1; } max = (int)fmax(max, degree);//每遍历完一个元素，取最大的度 }
得到元素最多出现的次数后，再次遍历数组Nums，如果某个元素的degree=max，说明该元素就是出现次数最多的元素。由于可能出现多个这样的元素，因此要设置一个最多出现元素的数组most，将所有最多出现次数的元素存储到这个数组中。
degree = 1; int* most = (int*)malloc(sizeof(int) * numsSize); memset(most, 0, sizeof(int) * numsSize); int mostsize = 0; for (int i = 0; i < numsSize - 1; i++) { if (Nums[i] == Nums[i + 1]) degree++; else degree = 1; if (degree == max) { most[mostsize++] = Nums[i]; } }
三、完整代码
int cmp(const void* e1, const void* e2) { return *(int*)e1 - *(int*)e2; } int* find_mostnum(int* nums, int numsSize) { int* Nums = (int*)malloc(sizeof(int) * numsSize); memcpy(Nums, nums, sizeof(numsSize) * numsSize); qsort(Nums, numsSize, sizeof(int), cmp); int degree = 1; int max = 0; for (int i = 0; i < numsSize - 1; i++) { if (Nums[i] == Nums[i + 1]) degree++; else degree = 1; max = (int)fmax(max, degree); } degree = 1; int* ans = (int*)malloc(sizeof(int) * numsSize); memset(ans, 0, sizeof(int) * numsSize); int ansSize = 0; for (int i = 0; i < numsSize - 1; i++) { if (Nums[i] == Nums[i + 1]) degree++; else degree = 1; if (degree == max) ans[ansSize++] = Nums[i]; } return ans; } int main() { int nums[] = { 1,2,2,3,1 }; int* ret = find_mostnum(nums, 5); for (int i = 0; i < 5; i++) { printf("%d ", ret[i]); } printf("\n"); return 0; }
