一. 简介
本文记录力扣网上编程题目，主要涉及数组方面的，以 C语言实现。
二. 力扣网C语言编程题：多数元素
多数元素
给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于[ n/2 ] 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1：
输入：nums = [3,2,3]
输出：3
示例 2：
输入：nums = [2,2,1,1,1,2,2]
输出：2
提示：
n == nums.length
1 <= n <= 5 * 104
-109 <= nums[i] <= 109
进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。
题目分析：
如果将数组中元素按照递增或递减的方式排序，那么，小标为 [n/2] 的元素一定是要找的元素（即出现次数大于 n/2的元素）；
下面的图中解释了为什么这种策略是有效的。在下图中，第一个例子是 n 为奇数的情况，第二个例子是 n 为偶数的情况。
对于每种情况，数组上面的线表示如果众数是数组中最小值时覆盖的下标，数组下面的线表示如果众数是数组中最大的数时覆盖的下标；对于其他情况，这条线会在这两种极端情况的中间，对于这两种极端情况，它们会在 n/2下标处会有重叠。
解题思路一：（排序返回 index为 n/2 的元素）
1. 对数组进行排序，要进行快速排序，使用 qsort函数（冒泡法排序的话，则需要再加其他处理，而不能完成冒泡法后返回 nums[n/2]元素，否则，会超过时间限制）；
2. 返回元素 nums[n/2] ；
C语言实现如下：
#include <stdio.h>
//从小到大排序
int compare(const void* a, const void* b) {
return *(int*)a - *(int*)b;
}
int majorityElement(int* nums, int numsSize) {
if((nums == NULL) || (numsSize <= 0)) {
return 0;
}
qsort(nums, numsSize, sizeof(int), compare);
int index = numsSize/2;
return nums[index];
}以冒泡法C语言实现：
int majorityElement(int* nums, int numsSize) {
if((nums == NULL) || (numsSize <= 0)) {
return -1;
}
int i, j;
int exchange_flag = 0;
//外层循环控制排序轮数：共n-1轮
for(i = 0; i < numsSize-1; i++) {
exchange_flag = 0;
//内层循环控制每一轮比较次数：每次减少i次比较
for(j = 0; j < numsSize-i-1; j++) {
//如果当前元素大于后一个元素
if(nums[j] > nums[j+1]) {
int tmp = nums[j];
nums[j] = nums[j+1];
nums[j+1] = tmp;
//标记发生了交换
exchange_flag = 1;
}
}
//每轮比较结束后判断 exchange_flag
//如果本轮未发生交换，说明数组已完全有序
if(exchange_flag == 0){
break;
}
}
return nums[numsSize/2];
}可以看出，冒泡法进行过程中，加入了标志位，每轮如果有交换则 exchange_flag标志置1，如果某一轮比较没有一次交换，说明数组已经有序，提前跳出循环。
最后返回元素 nums[numsSize/2]；
解题思路二：（摩尔投票法）
摩尔投票法思路，假如数组中每个元素出现的次数进行计数，那么，出现一次的计数器计为1，出现2次的计为2，...以此类推，那么出现次数超过 n/2的众数的计数次数肯定是过半了，那么，众数的次数-所有元素出现的次数一定是 大于 0的数；
具体方法：
1. 定义一个计数器，一个被投票对象；
2. 对数组进行遍历，判断当前元素是否与被投票对象相等。如果相等则 计数器自增；
否则， 计数器自减，判断 计数器 是否小于0，是则更换被投票对象，计数器更改为 1；
3. 最后，返回被选的对象；
C语言实现如下：
int majorityElement(int* nums, int numsSize) {
if((nums == NULL) || (numsSize <= 0)) {
return -1;
}
int count = 1; //计数器：记录当前候选元素的票数
int voted_object = nums[0];//候选元素：当前可能的多数元素
//遍历数组元素
for(int i = 1; i < numsSize; i++) {
//当前元素是否 == 被投票对象，是的计数器自增
if(nums[i] == voted_object) {
count++;
}
else { //当前元素是否 != 被投票对象，则计数器减1
count--;
//计数器 < 0，则更换被选对象，计数器count将次数置1
if(count < 0) {
voted_object = nums[i];
count = 1;
}
}
}
return voted_object;
}