首页 > 代码库 > LintCode-Majority Number
LintCode-Majority Number
Given an array of integers, the majority number is the number that occurs more than half of the size of the array. Find it.
Example
For [1, 1, 1, 1, 2, 2, 2], 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: find a majority number 5 */ 6 public int majorityNumber(ArrayList<Integer> nums) { 7 if (nums==null || nums.size()==0) return -1; 8 int len = nums.size(); 9 10 int cur = nums.get(0);11 int count = 1;12 for (int i=1;i<len;i++){13 if (cur!=nums.get(i)){14 count--;15 if (count==0){16 cur = nums.get(i);17 count=1;18 }19 } else {20 count++;21 }22 }23 24 return cur;25 }26 }
LintCode-Majority Number
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。