《LeetCode刷题》—169. 多数元素

《LeetCode刷题》—169. 多数元素

一、题目内容

原题连接：https://leetcode.cn/problems/majority-element/

题目：

二、个人答案（Java）

思路：先判断是否为一个元素，是就直接输出，不是就进行下面操作：1.排序 2.遍历数组判断前后元素相同的次数，用一个遍历a去记录，当a+1大于了题目要求的n+1之和就输出该元素，（相同的次数+1才等于出现的次数，比如【2,2,1,1,1,2,2】，排序后为【1,1,1,2,2,2,2】，第一个2和第二个相同2，第二个2和第三个2相同，第三个2和第4个2相同，这是相同总次数为3次，元素出现次数则为4次）

代码：

class Solution22 {
    public int majorityElement(int[] nums) {
        //如果只有一个元素就直接输出这个元素
        if (nums.length==1){
            return nums[0];
        }
        //先排序
        Arrays.sort(nums);
        //a值来确定啥时候终止循环
        int a=0;
        //遍历数组
        for (int i = 1; i <nums.length ; i++) {
            //如果当前元素和前一个元素相同则a+1，出现了不相同就a归零
            if (nums[i]==nums[i-1]){
                a++;
            }else {
                a=0;
            }
            //每次循环都判断a值是不是比nums.length/2-1小，这里因为计算出来的a值是元素出现的总次数-1，所以比较值也减一
            //循环的时候改变a的值相当于是相同元素的次数（注意是次数），但是这种计算方式没有计算该元素第一次出现，也就是他本身，所以出现的次数其实要加一，这里就移到不等号右边，减一了
            if (a>nums.length/2-1){
                return nums[i];
            }
;       }
        return 0;
    }
}

三、官方答案（Java）

这个题官方解题方法很多，这里放一样先排序的方法，应该也是最简方法

方法一：排序

思路：如果将数组 nums 中的所有元素按照单调递增或单调递减的顺序排序，那么下标为[n/2] 的元素（下标从 0 开始）一定是众数。

代码：

class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length / 2];
    }
}

答案来源：

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/majority-element/solution/duo-shu-yuan-su-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。