leetcode每日一题——169.多数元素（面试经典150题）_2.给定一个大小为n的数组nums,返回其中的多数元素。多数元素是指在数组中出现次数

一、题目描述与要求

169. 多数元素 - 力扣（LeetCode）

题目描述

给定一个大小为 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

---

二、解题思路

总的思路：

       首先理解题目要求，题目很简单，就是要找出数组中出现次数大于n/2的元素（多数元素），因而我们只需要对整个数组进行遍历，依次统计每个元素出现的次数，然后将其与n/2进行比较，修改最终结果，然后返回。整体思路很简单，实现起来也很简单。

        按照上述思路的方法，我们直接采用嵌套for循环来统计每一个元素出现的次数并进行比较得到最终结果，可知这一方法的时间复杂度O(n²)，当数组元素过多时会出现超时的情况，因而我们可以想一下如何去优化代码，使得其只使用一层for循环，将时间复杂度降到O(n)。

       首先这一层for循环肯定也是对整个数组的遍历，并且是用来统计出现次数的，也就是相当于嵌套循环方法中的第二层for循环的功能，那我们要如何去选择数组中的元素与数组中的其他元素进行比较呢，那就是利用一个辅助变量，将数组的第一个元素赋值给它，以其作为入口与数组中的其他元素进行比较，如果遇到相等的元素，则次数count++，如果不相等，则次数count--。当count<0时就代表此时辅助元素不是多数元素，因为有另一个出现次数大于它的，因而更新辅助变量为当前所比较的元素。然后重复上述步骤。

具体步骤：

①定义辅助变量result与count，并赋初值

②遍历数组统计元素出现次数

③返回最后结果result

---

三、具体代码【C语言】

①嵌套循环【超时 时间复杂度O（n²）】

int majorityElement(int* nums, int numsSize) {
    int result = 0;
    int count;
    for (int i = 0; i < numsSize; i++) {
        count = 1;
        for (int j = 0; j < numsSize; j++) {
            if (j != i) {
                if (nums[i] == nums[j]) {
                    count++;
                }
            }
        }
        if (count > (numsSize / 2)) {
            result = nums[i];
        }
    }
    return result;
}

②优化① 【时间复杂度O（n）】

int majorityElement(int* nums, int numsSize){
    int result=nums[0];
    int count=1;
    for(int i=1;i<numsSize;i++){
        if(nums[i]==result){ //找到相等的，次数增加
            count++;
        }
        else//不相等，次数减少
        {
            count--;
            if(count<0)//该元素不是多数元素，更新次数与结果
            {
                result=nums[i];
                count=1;
            }
        }
    }
    return result;
}