本文主要是介绍leetcode oj java 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.
二、解决思路：
算法书中非常经典的一道题目。
数组中的出现次数超过数组长度的一半，说明它出现的次数大于其余数字出现的次数之和。考虑在遍历数组的时候保存两个值： 数字index, 以及数字出现的次数num
遍历数组。如果下一个数字k和Index 的值相同，那么次数num+1， 如果不同，次数num-1; 如果num<0 , 把index 设置为k。 遍历结束的时候留下的index 是数组中出现次数
超过数组长度一半的数字。
三、代码：
package T12;/*** @author 作者 : xcy* @version 创建时间：2016年12月31日 下午2:42:54* 类说明*/
public class t169 {public static void main(String[] args) {// TODO Auto-generated method stubint[] nums = { 1, 2, 1, 2, 3 };System.out.println(majorityElement(nums));}public static int majorityElement(int[] nums) {int index = nums[0];int num = 1;for (int i = 1; i < nums.length; i++) {if (index == nums[i]) {num++;} else {num--;}if (num < 0) {index = nums[i];num = 1;}}return index;}}
这篇关于leetcode oj java 169. Majority Element的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
