LeetCode169-多数元素

 

非商业,LeetCode链接附上:

https://leetcode-cn.com/problems/majority-element/

进入正题。

 

题目:

给定一个大小为 n 的数组,找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的,并且给定的数组总是存在多数元素。

 

示例:

示例 1:

输入:[3,2,3]
输出:3


示例 2:

输入:[2,2,1,1,1,2,2]
输出:2
 

进阶:

尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。

 

代码实现:

//解决的方法比较多,这里只介绍一种,也是最开始使用,并官方题解里面详细介绍的
//Boyer-Moore 投票算法
public int majorityElement(int[] nums) {
        int count = 0;
        Integer candidate = null;

        for (int num : nums) {
            if (count == 0) {
                candidate = num;
            }
            count += (num == candidate) ? 1 : -1;
        }

        return candidate;
}

//以上方法改进版(上面的方法执行时间比较长,可能是因为使用了Integer,装箱拆箱需要时间)
public int majorityElement(int[] nums) {
        
        //由于题目中提到数组非空,因此不再进行非空判断
        int count = 1;
        int candicate = nums[0];

        for(int i = 1; i < nums.length; i++) {
            if(count == 0) {
                candicate = nums[i];
            }
            count += (candicate == nums[i])? 1 : -1;
        }

        return candicate;        
}
//时间复杂度O(n),空间复杂度O(1)
    

  

思考:

题目的解决方案不止一种,可能就像人生的路不止一条吧,但就像算法追求高效、清晰等,人生的路也不能走的太糙吧。

 

--End

 

上一篇:flink 1.9.0 编译:flink-shaded-hadoop-2 找不到


下一篇:Python绘图Turtle库详解