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

leetcode筆記:Majority Element II

編輯:C++入門知識

leetcode筆記:Majority Element II


一. 題目描述

Given an integer array of size n, find all elements that appear more than ? n/3 ? times. The algorithm should run in linear time and in O(1) space.

Hint:

How many majority elements could it possibly have?

二. 題目分析

題目大意是,給定一個大小為n的整數數組,從中找出所有出現次數超過 ? n/3 ? 的元素。要求算法滿足線性時間復雜度和O(1)的空間復雜度。

提示:一共可能有多少個majority elements?

首先應該意識到一點: 在一個數組中出現超過三分之一次的元素,這樣的元素最多只能有兩個,超過兩個就與命題相矛盾。該題與題目Majority Element的思路相類似,只是該題中最多可能出現兩個majority elements。在這裡,要求線性時間復雜度和O(1)的空間復雜度,唯有使用摩爾投票法的思想來解。

摩爾投票法的基本思想很簡單,在每一輪投票過程中,從數組中找出一對不同的元素,將其從數組中刪除。這樣不斷的刪除直到無法再進行投票,如果數組為空,則沒有任何元素出現的次數超過該數組長度的一半。如果只存在一種元素,那麼這個元素則可能為目標元素。

三. 示例代碼

// C++代碼
class Solution {
public:
    vector majorityElement(vector& nums) {
        vector result;
        if (nums.size() == 0) return result;
        int num1 = INT_MAX, num2 = INT_MAX;
        int time1 = 0, time2 = 0;
        for (int i = 0; i < nums.size(); ++i)
        {
            if (num1 == nums[i]) ++time1;
            else if (num2 == nums[i]) ++time2;
            else if (time1 == 0)
            {
                time1 = 1;
                num1 = nums[i];
            }
            else if (time2 == 0)
            {
                time2 = 1;
                num2 = nums[i];
            }
            else
            {
                --time1;
                --time2;
            }
        }
        time1 = 0, time2 = 0;
        for (int i = 0; i < nums.size(); ++i)
        {
            if (num1 == nums[i]) ++time1;
            else if (num2 == nums[i]) ++ time2;
        }
        if (time1 > nums.size() / 3) result.push_back(num1);
        if (time2 > nums.size() / 3) result.push_back(num2);
        return result;
    }
};
// Python代碼
class Solution:
    # param {integer[]} nums
    # return integer[]
    def majorityElement(self, nums):
        if not nums:
            return []
        num1, num2, time1, time2 = None, None, 0, 0
        for num in nums:
            if num1 == num:
                time1 += 1
            elif num2 == num:
                time2 += 1
            elif time1 == 0:
                num1, time1 = num, 1
            elif time2 == 0:
                num2, time2 = num, 1
            else:
                time1, time2 = time1 - 1, time2 - 1
        numSize = len(nums)
        return [n for n in (num1, num2) if
                n is not None and nums.count(n) > numSize / 3]

四. 小結

關於摩爾投票法:http://mabusyao.iteye.com/blog/2223195

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