星空网 > 软件开发 > Java

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.NoteThere is only one majority number in the arrayExampleFor [1, 2, 1, 2, 1, 3, 3] return 1ChallengeO(n) time and O(1) space

三三抵销法,但是也有需要注意的地方:

1. 我们对cnt1,cnt2减数时,相当于丢弃了3个数字(当前数字,candidate1, candidate2)。也就是说,每一次丢弃数字,我们是丢弃3个不同的数字。

而Majority number超过了1/3所以它最后一定会留下来。

设定总数为N, majority number次数为m。丢弃的次数是x。则majority 被扔的次数是x

而m > N/3, N - 3x > 0. 

3m > N,  N > 3x 所以 3m > 3x, m > x 也就是说 m一定没有被扔完

最坏的情况,Majority number每次都被扔掉了,但它一定会在n1,n2中。

2. 为什么最后要再检查2个数字呢(从头开始统计,而不用剩下的count1, count2)?因为数字的编排可以让majority 数被过度消耗,使其计数反而小于n2,或者等于n2.前面举的例子即是。

另一个例子:

1 1 1 1 2 3 2 3 4 4 4 这个 1就会被消耗过多,最后余下的反而比4少。

 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     // write your code 8     int candidate1 = 0; 9     int candidate2 = 0;10     int count1 = 0;11     int count2 = 0;12     for (int elem : nums) {13       if (count1 == 0) {14         candidate1 = elem;15       }16       if (count2 == 0 && elem != candidate1) {17         candidate2 = elem;18       }19       if (candidate1 == elem) {20         count1++;21       }22       if (candidate2 == elem) {23         count2++;24       }25       if (candidate1 != elem && candidate2 != elem) {26         count1--;27         count2--;28       }29     }30     31     count1 = 0;32     count2 = 0;33     for (int elem : nums) {34       if (elem == candidate1) count1++;35       else if (elem == candidate2) count2++;36     }37     return count1>count2? candidate1 : candidate2;38   }39 }

 




原标题:Lintcode: Majority Number II

关键词:

*特别声明:以上内容来自于网络收集,著作权属原作者所有,如有侵权,请联系我们: admin#shaoqun.com (#换成@)。

海外版“淘宝直播”?亚马逊在视频营销的又一次试水:https://www.ikjzd.com/articles/21662
跨境电商如何找货源?7种途径帮你找到货源!:https://www.ikjzd.com/articles/21665
收藏 | 亚马逊ERP管理系统运行流程详解!:https://www.ikjzd.com/articles/21667
5月1日开始强制实施:eBay提升曝光量和销量的刊登规则:https://www.ikjzd.com/articles/21668
亚马逊线上工具大起底(九):邮件回复工具上篇:https://www.ikjzd.com/articles/2167
亚马逊运营工作有哪些?怎么运营好亚马逊店铺?:https://www.ikjzd.com/articles/21671
长治婚庆女司仪和主持人:https://www.vstour.cn/a/366176.html
北京丰台区水上乐园哪家好玩?:https://www.vstour.cn/a/366177.html
相关文章
我的浏览记录
最新相关资讯
海外公司注册 | 跨境电商服务平台 | 深圳旅行社 | 东南亚物流