非商业,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