給定一組數(shù)，有一個數(shù)在這組數(shù)里的出現(xiàn)次數(shù)超過n/2次。

求出這是哪個數(shù)

https://leetcode.com/problems/majority-element/

一開始考慮的方是將所有數(shù)轉(zhuǎn)化為二進制，那么對于這些二進制數(shù)來說。

其每一位上必然是出現(xiàn)次數(shù)最多的數(shù)決定了它是1還是0。

例如，將每個二進制數(shù)的最低位加起來，得到一個sum。

那么如果sum/nums.length大于0.5那么這個majority number在最低位必然是1

反之必然為0。這樣就可以把所有的位置求出來。AC了

但是網(wǎng)上查到了一個更好的解法。

即，每出現(xiàn)一對不同的數(shù)，就刪除它，那么到最后剩下的那個數(shù)必然是所求的數(shù)。

網(wǎng)上給出的代碼也極為精巧

1 public int majorityElement(int[] nums) { 2 int count = 0, candidate = -1; 3 for (int i = 0; i < nums.length; i++) { 4 if (count == 0) { 5 candidate = nums[i]; 6 count = 1; 7 } else if (candidate == nums[i]) { 8 count++; 9 } else { 10 count--; 11 } 12 } 13 return candidate; 14 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/elnino/p/5626241.html

總結(jié)

以上是生活随笔為你收集整理的leetcode majority number的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。