当前位置:首页 » 编程语言

leetcode_Majority Element

2015-08-07 09:36 本站整理 浏览(131)

描述:

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

思路:

1.对于这种问题,相信很多人都会想起来直接对数组拍下序,然后取中间值即可return nums[nums.length/2];地球人都知道,哈哈。。。Time:O(n(log(n)),Space:O(k)

2.啥?还有更好的方法?对,其实还真有,先找第一个数字curNum作为锚,count统计curNum目前为止出现的次数,依次遍历数组nums[i],如果nums[i]==curNum,count++;如果不等呢,count--,此时若count==0;再换锚点为curNum=nums[i],并令count==1

3.重复2中的步骤直至遍历完所有的数组元素,那么最后剩下的nagecurNum就是在数组中出现次数大于一半的数字。

代码:

public int majorityElement(int[] nums) {
        int count=1,curNum=nums[0];
        for(int i=1;i<nums.length;i++)
        {
            if(nums[i]==curNum)
                count++;
            else
            {
                count--;
                if(count==0)
                {
                    curNum=nums[i];
                    count=1;
                }
            }
        }
        return curNum;
    }