力扣网C语言编程题：多数元素

一. 简介

本文记录力扣网上编程题目，主要涉及数组方面的，以 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 {  //当前元素是否 != 被投票对象，则计数器减1count--;//计数器 < 0，则更换被选对象，计数器count将次数置1if(count < 0) { voted_object = nums[i];count = 1;}}}return voted_object;
}