題目
描述
給定一個整型數(shù)組吧享，找出主元素，它在數(shù)組中的出現(xiàn)次數(shù)嚴格大于數(shù)組元素個數(shù)的二分之一譬嚣。
樣例
給出數(shù)組[1,1,1,1,2,2,2]钢颂，返回 1
解答
思路
看到這個題目，第一反應(yīng)是排序后取中間數(shù)拜银，這沒什么好說的殊鞭。
這個題目的挑戰(zhàn)是時間復(fù)雜度為O(n)，空間復(fù)雜度是O(1)尼桶。這個有點意思操灿。
如果一個數(shù)組存在主元素，那么在數(shù)組中刪除兩個不同的數(shù)泵督，對于主元素的地位是沒有影響的牲尺。根據(jù)這個思路設(shè)計算法。
代碼
public class Solution {
/**
* @param nums: a list of integers
* @return: find a majority number
*/
public int majorityNumber(ArrayList<Integer> nums) {
// write your code
/**
* count: 統(tǒng)計當前認為的主元素的數(shù)量
* seed: 當前認為的主元素
* n: 數(shù)組長度
**/
int count = 0, seed = nums.get(0), n = nums.size();
//從兩頭往中間循環(huán)
for(int i = 1; i<n/2; i++){
//若兩數(shù)相等，主元素備選
if(nums.get(i) == nums.get(n-i)){
//若當前沒有認為的主元素
if(count == 0){
//那么取當前數(shù)為主元素
seed = nums.get(i);
//統(tǒng)計加一
count++;
}
//若已有認為的主元素
else{
// 若與主元素相等谤碳，統(tǒng)計量加一
if(seed == nums.get(i)) count++;
// 若與主元素不等溃卡，統(tǒng)計量減一
// 這里如果減小到0了，可能會產(chǎn)生主元素切換
else count--;
}
}
}
//統(tǒng)計主元素出現(xiàn)的次數(shù)
for(int i = 0;i<n;i++){
if(nums.get(i) == seed){
count++;
}
}
//超過一半才被認為是主元素
if(count >= n/2){
return seed;
}
//提交了幾次發(fā)現(xiàn)如果沒超過一半需要返回最后的元素
else{
return nums.get(n-1);
}
}
}
