主元素

题目

给定一个整型数组,找出主元素,它在数组中的出现次数严格大于数组元素个数的二分之一。
http://www.lintcode.com/zh-cn/problem/majority-number/

分析

必须要理解“主元素在数组中的出现次数严格大于数组元素个数的二分之一”的含义,它意味着,数组中有超过一半的元素是主元素。可以得出推论:

  • 如果将数组排序后(无论升降),array[n/2]的元素必然是主元素
  • 由于主元素占据绝对数量优势,任意取两个元素,若它们不想等,就删掉这两个元素,到最后剩下的元素必然是主元素

因此,可以得出相应的两种解法:排序法和消除法。

若要使用排序法,则可以通过堆排序或者快排,然后取n/2位置的元素,就是主元素。

若使用消除法,则依次从首尾取出元素进行比较,若两者不同,则将二者删除,重新开始比较;若两者相同,则从后往前试探,直至首尾的游标相遇。

代码

这里只给出消除法的代码:


public class Solution {

    /*
     * @param nums: a list of integers
     * @return: find a  majority number
     */
    public int majorityNumber(List nums) {
        int i=0, j=nums.size()-1;
        
        int sb = nums.get(0).intValue();
        
        for(;i < j;){
          if(nums.get(j).intValue() != sb){
              nums.remove(j);
              nums.remove(i);
              j = nums.size()-1;
              i = 0;
              sb = nums.get(0).intValue();
              continue;
          }else{
              j--;
              continue;
          }
        }

        return nums.get(0).intValue();
    }
}

进一步优化

消除法并没有做到O(n) 的时间复杂度,同时,主元素与非主元素的抵消,也不必真的去删除元素,通过一个额外的计数器即可,其算法流程如下:

  • 将数组中的第一个元素作为备选主元素,计数器记为1
  • 开始遍历后续元素,若与当前备选主元素相同,计数器增加1,若不同,则计数器减去1
  • 当计数器归零时,要重新选择备选主元素,并将计数器置为1
  • 遍历结束后,得到主元素,以及主元素比其他非主元素多出的个数

代码实现很简单,略过。

Show Comments

Get the latest posts delivered right to your inbox.