169. Majority Element

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.

读题

题目的意思是给定一个不为空的数组，找到主要的元素，主要的元素的定义是出现次数大于数组元素n的一半，并且假设这样的主要元素一定是存在的

思路

先假定第一个元素是数组的主要元素，k=1，主要元素的下标是index，这样的话遍历一次数组，如果元素i和主要元素是相同的就k++，如果元素和主要元素是不同的就k--，如果此时k==0，就更换index为当前的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];
    }
}