Problem Description:
Given an array of size
n
, find the majority element. The majority element is the element that appears
more than
⌊ n/2 ⌋
times.You may assume that the array is non-empty and the majority element always exist in the array.
Example 1:
Input: [3,2,3] Output: 3
Example 2:
Input: [2,2,1,1,1,2,2] Output: 2
Analysis:
本题的思路也比较简单,因为队列中最多的元素的个数大于队列长度的一半,因此维护一个变量用来记录队列中多次出现的变量。
Code:
class Solution {
public int majorityElement(int[] nums) {
int prev = nums[0];
int cnt = 1;
for(int i = 1; i < nums.length; i++) {
if(nums[i] != prev) {
cnt--;
} else if(nums[i] == prev) {
cnt++;
}
if(cnt <= 0) {
prev = nums[i];
cnt = 1;
}
}
return prev;
}
}
版权声明:本文为zzyy17原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。