題目
數組中有一個數字出現(xiàn)的次數超過數組長度的一半付枫，請找出這個數字经磅。
你可以假設數組是非空的，并且給定的數組總是存在多數元素。
示例 1:
輸入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
輸出: 2
限制：
1 <= 數組長度 <= 50000
Hash 算法
class Solution {
public int majorityElement(int[] nums) {
int half = nums.length / 2;
Map<Integer, Integer> map = new HashMap<>();
for (int n : nums) {
int count = map.getOrDefault(n, 0);
count++;
if (count > half) {
return n;
}
map.put(n, count);
}
return nums[0];
}
}
投票算法
class Solution {
public int majorityElement(int[] nums) {
int x = 0, votes = 0;
for (int n : nums) {
if (votes == 0) x = n;
votes += (x == n) ? 1 : -1;
}
return x;
}
}
