[leetcode]Majority Element

作者:luozhipeng   发表日期:2015-7-12  浏览:790次

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.

element

题意:找出数组的主元素(占比大于一半的元素)。

 

输入:数组

返回:主元素。

 

思路:1.快速排序取中间一个。2.当数组大小为奇数时,判断第一个元素是否为主元素,若不是则删除,否则返回该元素;偶数情况下,对比相邻元素,若相同则删除其中一个,若不同则都删除。直到只剩一个元素返回。


class Solution {
public:
/*1
    int majorityElement(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        return(nums[nums.size()/2]);
    }
*/
     int majorityElement(vector<int>& nums) {
        int size,count,tmp;
        while(true){
            size = nums.size();
            if(size == 1)
                return nums[0];
            if(size%2 == 1){
                tmp = nums[0];
                count = 1;
                for(int i = 1; i < size; ++i){
                    if(tmp == nums[i])
                        ++count;
                    if(count > (size >> 1))
                        return tmp;
                }
                --size;
                nums.erase(nums.begin());
            }
            for(int i = size - 1; i > 0; i -= 2){
                if(nums[i] != nums[i-1])
                    nums.erase(nums.begin() + i);
                nums.erase(nums.begin() + i - 1);
            }
        }
    }  
};

标签:

本文固定链接: http://www.luozhipeng.com/?p=407
转载请注明: luozhipeng 2015-7-12 于 罗志鹏的BLOG 发表

上一篇: :下一篇
评论:请安装多说插件!
返回顶部