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.
解题思路:
编程之美P130(寻找发帖水王)原题,如果删除两个不同的num,那么剩下的num,最多的元素依旧出现多于⌊ n/2 ⌋
times
JAVA实现如下:
public int majorityElement(int[] nums) {
LinkedList<Integer> list=new LinkedList<Integer>();
for(int num:nums){
if(list.isEmpty())
list.add(num);
else if(num==list.getLast())
list.add(num);
else list.remove(list.size()-1);
}
return list.get(0);
}