程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> leetcode169——Majority Element (C++),majorityelement

leetcode169——Majority Element (C++),majorityelement

編輯:C++入門知識

leetcode169——Majority Element (C++),majorityelement


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.

個人博客:http://www.cnblogs.com/wdfwolf3/。

題目比較好理解,在含有n個元素的數組中找出出現次數超過⌊n/2⌋的元素,假設數組不為空而且這個數是一定存在的。

1.moore-voting算法

這個算法就是為解決這個問題誕生的,主要思想就是找出一對不同的元素就去掉它們,最後剩下的一定是所找的元素。

class Solution { public: int majorityElement(vector<int>& nums) { int result=nums[0],count,i; for(i=1,count=1;i<nums.size();i++) { count+=nums[i]==result?1:-1; if(count>nums.size()/2) break; if(count==0) { count=1; result=nums[i+1]; i++; } } return result; } } View Code(16ms)

2.hash

遍歷數組,利用hash方式記錄元素出現的次數,當某個元素次數超過⌊n/2⌋時,即為我們要找的。

class Solution { public: int majorityElement(vector<int>& nums) { unordered_map<int,int> m; int i; for(i=0;i<nums.size();i++) { if(++m[nums[i]]>(nums.size()/2)) return nums[i]; } return nums[0]; } }; View Code(28ms)

3.sorting

對數組進行排序,由於要找的元素超過半數,所以下標n/2的元素一定是它,這裡總數奇偶不影響,可以自己舉例驗證一下。

class Solution {
public:
    int majorityElement(vector<int>& nums) {      //40ms
        sort(nums.begin(),nums.end());
        return nums[nums.size()/2];
    }
};

4.randomization

隨機選取數組中的一個數,驗證它是不是超過半數的數字。時間最快,有一半幾率選中,當然最壞的情況比較糟糕,但這不重要,就像快速排序時間復雜度一樣。

class Solution { public: int majorityElement(vector<int>& nums) { srand(unsigned(time(NULL))); int tmp,i,count; while(true) { tmp=nums[rand()%nums.size()]; for(i=0,count=0;i<nums.size();i++) { if(tmp==nums[i]) count++; if(count>nums.size()/2) return tmp; } } } }; View Code(16ms)

5.bit manipulation

就是把數字都作為二進制處理,每個二進制位上的n個bit相加看是否大於n/2,大於的話這一位上是1,小於的話就是0,把32位都這麼處理完就知道結果是多少了。

class Solution { public: int majorityElement(vector<int>& nums) { int i,j,count,major=0; for(i=0;i<32;i++) { for(j=0,count=0;j<nums.size();j++) { if((nums[j]>>i&1)==1) count++; } if(count>nums.size()/2) major+=(1<<i); } return major; } } View Code(40ms)

6.分治

處理這種問題都可以嘗試下分治方法,這道題也可以不過感覺太麻煩,就不寫了。

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved