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.
讀題
題目的意思是給定一個(gè)不為空的數(shù)組，找到主要的元素，主要的元素的定義是出現(xiàn)次數(shù)大于數(shù)組元素n的一半秒拔，并且假設(shè)這樣的主要元素一定是存在的
思路
先假定第一個(gè)元素是數(shù)組的主要元素召烂，k=1姓赤，主要元素的下標(biāo)是index椅寺，這樣的話遍歷一次數(shù)組，如果元素i和主要元素是相同的就k++巫员，如果元素和主要元素是不同的就k--，如果此時(shí)k==0光酣，就更換index為當(dāng)前的i
題解
public class Solution {
public int majorityElement(int[] nums) {
if (nums.length == 1)
return nums[0];
int index = 0;
int k = 1;
for (int i = 1; i < nums.length; i++) {
if (nums[i] == nums[index]) {
k++;
} else if (nums[i] != nums[index]) {
k--;
if (k == 0){
index = i;
k = 1;
}
}
}
return nums[index];
}
}
