首页 > 代码库 > LintCode-Majority Number II
LintCode-Majority Number II
Given an array of integers, the majority number is the number that occurs more than 1/3 of the size of the array.
Find it.
Note
There is only one majority number in the array
Example
For [1, 2, 1, 2, 1, 3, 3] return 1
Challenge
O(n) time and O(1) space
Solution:
1 public class Solution { 2 /** 3 * @param nums: A list of integers 4 * @return: The majority number that occurs more than 1/3 5 */ 6 public int majorityNumber(ArrayList<Integer> nums) { 7 if (nums.size()==0) return -1; 8 if (nums.size()<3) return nums.get(0); 9 int len = nums.size();10 11 int n1 = nums.get(0), n2 = 0;12 int count1 = 1, count2 = 0;13 14 for (int i=1;i<len;i++)15 if (nums.get(i)==n1)16 count1++;17 else if (nums.get(i)==n2)18 count2++;19 else {20 if (count1==0) {21 n1 = nums.get(i);22 count1 = 1;23 } else if (count2==0){24 n2 = nums.get(i);25 count2 = 1;26 } else {27 count1--;28 count2--;29 }30 }31 32 if (count1!=0 && count2!=0){33 count1 = 0;34 count2 = 0;35 for (int i=0; i<len;i++)36 if (nums.get(i)==n1) count1++;37 else if (nums.get(i)==n2) count2++;38 if (count1>len/3) return n1;39 else return n2;40 } else if (count1!=0) return n1;41 else return n2;42 43 }44 }
LintCode-Majority Number II
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。