Majority Element--LeetCode

刺骨的言语ヽ痛彻心扉 2022-08-07 13:34 108阅读 0赞

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.

思路：可以参考快速排序的定位方法，参照任何一个元素，进行重新一次排序，之后相同的元素就相邻，既然这个元素多余总元素个数的n/2，那么遍历这个数组，对于此元素和n/2之后的元素相等，说明就是这个元素。

#include <iostream>
    #include <vector>
    using namespace std;
    
    int majorityElement(vector<int> &num) 
    {
        int i,j;
        int key = num[0];
        for(i=-1,j=0;j<num.size();j++)
        {
            if(num[j]<key)
            {
               i++;
               swap(num[i],num[j]);
            }                              
        } 
        
        for(i=0;i<num.size()/2;i++)
        {
            key = num[i+num.size()/2];
            if(num[i] == key)
             return key;                        
        }       
    }
    
    int main()
    {
        int array[]={3,2,4,5,2,2,4,2,2,2,2,7};
        vector<int> vec(array,array+sizeof(array)/sizeof(int));
        cout<<majorityElement(vec);
        system("pause");
        return 0;
        }

总结：这里借助了快速排序的partation的思想，将整个程序按照某一个元素进行分割，分割以后相同的元素肯定是相邻，那么可以根据某一个元素n/2之后的元素是否相等，仍然相等，说明这个元素就是所要求的元素。

也可以使用另一种方案，比如我们遍历真个数组中的元素，我们记录元素出现的次数，如果和当前记录的元素不同，那么次数减1，直到次数为0为止，同时更新当前记录的元素的值。当前元素的次数为1